CCC 2010

( Reminder:Deadline for submitting to special issue of Theory of Computing in honor of Rajeev Motwani is July 30. See here. )

CCC 2010!

1. Ran Raz gave an AWESOME invited talk on Parallel Repetition of two player games ( here are the slides). What was most striking to me is that this line of research lead to the solution of a math problem (the Foam Problem) which would seem to be completely unrelated to it. Has this happened before- research starting in TCS leads to the solution of a seemingly unrelated math problem? Of course, my question is ill defined since TCS, Math Problem and seemingly unrelated are not well defined.
2. The talks following Ran's were also on two player games so his talk was a great way to get you up to speed on what follows. I would recommend that the Program Committee try to do this in the future: have the invited talk be the first in a session on related material. (I also realize that this may be hard to pull off.)
3. Subhash Khot gave a good invited talk on The Unique Game Conjecture. (These Slides should soon be available soon on his website. There is already a written survey on the material on his website and also slides he gave at FOCS05 on UGC. Here is his webpage.) This conjecture has been a great breakthrough in that it gives us something reasonable to assume that gives approx lower bounds- some of which match the approx upper bounds. It has also had many other applications unforeseen even by Khot when he first conjectured it. (Over dinner Khot told me he is only 90% sure that it is true. Gee, I thought he would have more confidence than that!.)
4. The talks that followed Khot's talk were all on UGC, and that was a big win.
5. Oded Regev gave great invited talk on The Learning with Errors Problem. (Talk and paper are here.) This was a talk where I learned about a problem I had not heard of and its connections to other problems. One of the applications was crypto (not surprising- that is Regev's main area.) The talks that followed it did not connect to it as much as for the other invited talks. This does not take away from the fact that I learned stuff of interest that I did not know ANYTHING about before.
6. Jakob Nordstrom gave a nice talk On the relative strength of pebbling and resolution. I had not known that pebbling was used to give lower bounds on resolution and I look forward to reading his 200 page survey on this topic. (It is on his website.)
7. Eric Allender had a paper in the first CCC (called STRUCTURES then) on Auxiliary PDA's. Eric Allender had a paper in the 25th CCC on Auxiliary PDA's. An Auxiliary PDA is a PDA with an additional log space workspace. I look forward to an Eric Allender paper on Aux PDA's at the 50th CCC. Note that Eric has worked on many other things as well.
8. Hrbues, Wigderson, Yehudayoff had a paper on Relationless Completeness and Separations. The idea here is to take algebraic complexity and see if you can get lower bounds if you do not assume that the operations are associative or commutative. The good news is that they did! The bad news is that the bounds for the case where the operations are associative and communicative are as hard as they were when Valiant first proposed this model many years ago. Valiant was at the talk and told me later that he would have thought that there would be more progress by now.
9. Alexandra Kolla had a paper Spectral Algorithms for Unique games. She seems to think that the UGC is false!
10. Impagliazzo and Williams talk on Communication Complexity with Synchronized clocks was an interesting new model of Communication Complexity which was used to solve some problems in classical CC. Also easy to understand since it was the first talk on a model. I suspect that within 5 years people will be using hard math to study this model and the talks will be harder to follow.
11. Buhrman, Fortnow, Koucky, Loff's paper show us that random strings are powerful in Derandomization from Random Strings
12. The most depressing talk was Derandomizing Arthur-Merlin Games and approximate counting problems since it seemed to imply that we need lower bounds on circuits to get derandomization. Worth knowing but not good news.
13. Business Meetings and Spouses: I know of three people who brought their non-complexity spouses with them to Boston. (They went sightseeing during the conference.) There are three approaches to what to do the night of the business meeting. One went to the meeting and left the spouse at the Hotel. One skipped the meeting to be with their spouse. One brought the spouse to the meeting. What would you do?
14. Business meeting was uneventful. CCC11 will be in San Jose as part of FCRC, CCC12 will be in Portugal (this was already sort-of known). Next year we may be leaving the 10th century and rather than give out handwritten proceedings on parchment we will be doing something electronic. Valentine Kabanets and Dieter von Melkebeek will be on the CCC steering committee, replacing two people whose terms have expired.