The First China Symposium on Theoretical Computer Science, Day 1

The great Andrew Yao invites and many famous researchers come - what a great event, I'm very glad to have the opportunity to listen to interesting talks at the China Symposium on Theoretical Computer Science.

A brief summary of day 1.

A lot of history and high-level in the morning.

Ronald Graham gave a history of Steiner Trees. His introduction was in Chinese, very impressive, I didn't understand a word though... Next surprise, I didn't know that we don't even know whether Euclidean MST is in NP!

Christos Papadimitriou presented 6 to 8 examples where Computer Science proves its influence to other sciences. A very interesting one was the question whether an optimal system can have an internal conflict (Livnat Pippenger answer this question with yes in 2006), regarding the many internal conflicts in our brain... Then, he made a point that genetic algorithms don't prove useful for combinatorial problems as sexual reproduction favors low risk medium payoff such that we can mate with whoever we want to (Livnat, Papadimitriou 2007).

Avi Wigderson talked about reductions and the history of the PCP theorem.


The afternoon was more concrete.

Sanjeev Arora surveyed SDP and connections to high dimensional geometry. I understood the beginning, became tough towards the end.

Avrim Blum talked about Learning and Clustering. The properties of the similarity measure influence the algorithm to use to get a good clustering. Some problems in clustering are hard but they might be hard because of the model, while the actual problem might be a bit easier.

Maurice Herlihy showed that Renaming is Weaker than Set Agreement (a weaker form of consensus)

And finally, Nir Shavit showed Hashing for Multicore Architectures. It looks like the software will be the bottleneck in the future, hardware switches to Multicore Architectures and software cannot handle the synchronizations. We'll see. Maybe noone will buy the new hardware if the speed-off is too small.
The Recursive Split Ordering reminded me of something I've heard at NII, more to come about that.