Just finished the morning sessions of day one. I guess it's time for the standard disclaimer – the talks I blog about are those I happened to attend and should not be interpreted as the "best" or even my personal "favorite" results, etc. etc. etc.
So about the sessions. Session one started at 8.30 AM and I'm embarrassed to admit that despite being the "guest blogger" of FOCS I missed the first talk. Somehow research before 9.00 AM is akin to hard liquor before breakfast for me. I just can't stomach it. I caught the end of the talk though, and was shocked that the room was packed! I took a picture, try and see who isn't there. :)
The second session was much closer to my research area – algorithmic game theory – and hence I got much more from those talks. One particular nice result was that from the paper Mechanism Design via Differential Privacy. The authors introduce a new solution concept for mechanism design which resolves many of our frustrations with dominant strategy mechanism design, and they do so through a creative connection to a seemingly unrelated field – privacy.
Missing that first talk was a mistake. It was excellent. It followed exactly the lines Terence Tao suggested in his tutorial, a concrete application.
ReplyDeleteNominations for the official unofficial complexity blog FOCS awards:
Best jokes: Andrea Montanari
Best analogy: Anna Karlin (balloons)
Best session chair: Kamal Jain
Best talk: ?? still open..
Correction to anonymous 1:
ReplyDeleteThat was Nicole not Anna giving the talk.
Best analogy: Nicole Immorlica (balloons)
though of course the kudos for the analogy go to all authors.
I heard several comments in the halls on the first day about the high quality of the talks in general. One talk I really liked was Mihalis Yannakakis' talk on fixed points and approximating Nash equilibria. This is different from the Nash problem that is PPAD-complete in that the goal is to approximate a fixed point rather than find a point that is approximately fixed. Because 3-player Nash includes the Sum of Square Roots problem as a special case, this problem seems much harder (A nice result of the paper is that this version of 3-player Nash is as hard as the general problem of computing an approximation to a fixed point of an arithmetic circuit.)
ReplyDeleteBTW: The Sum of Square Roots problem is not well known but it probably should be: Given positive integers a_1,...,a_n, and k
is sum_i sqrt{a_i}<=k? It is open whether this is even in NP. Allender et. al. (2006) showed that it can be solved in the 4th level of the Counting Hierarchy P^{PP^{PP^{PP}}} (PSPACE was already known) but that seems to be the smallest complexity class so far. The issue is that the best we know is an exponential upper bound on the number of bits of precision required to separate the sum from k.