STOC 2008 begins. Victoria is a gorgeous city, if a bit sterile. The population feels mostly transient. The people are very friendly, and the streets are very clean. Most academic conversation turns eventually to one of two topics: Outcomes of the hiring season, and opinions on the "conceptual manifesto" (my naming); more on the latter topic in the business meeting post next.
The conference starts off strong, with Ran Raz presenting Anup Rao's optimal parallel repetition theorem for projection games (Anup had visa issues). Anup gives optimal bounds on the rate of decay of the value of a 2-player game repeated in parallel, in the case where the answers of one player determine the unique answer of the other player that causes the verifier to accept (this is the projection property). The decay rate was recently proved to be optimal by Raz, thereby disproving a strong parallel repetition theorem.
A special case of a projection game is a unique game, the topic of Prasad Raghavendra's paper Algorithms and inapproximability results for every CSP?. Prasad is one of our own, a theory student at UW; his paper was co-winner of the best paper award and sole winner of the best student paper award. For a few years now, since the KKMO max-cut paper, it has been suspected that there is an intimate connection between the unique games conjecture and the power of semi-definite programming in approximation algorithms, although it is only recently--in the work of Austrin--that this connection has begun to materialize explicitly. Prasad sets the connection in stone: He gives a general class of SDPs and a generic poly-time rounding algorithm for all of them, such that for any MAX k-CSP problem, the approximation bound achieved by his algorithm is best possible assuming the unique games conjecture. A key technical step involves converting any integrality gap for his SDP to a unique games hardness result. The talk is remarkably lucid and well-paced.
The other best paper winner is Harald Raecke, for his work "Optimal hierarchical decompositions for congestion minimization in networks." Raecke shows roughly that, given a graph G, there exists a family of trees such that any multi-commodity flow problem in G can be solved by first routing it in each of the trees (trivial), and then mapping a convex combination of those routings into G. The resulting routing in G has congestion within O(log n) of optimal. The mapping from the tree routings to routings in G is fixed, and in particular independent of the flow instance. This gives an O(log n)-approximate oblivious routing protocol, which is best-possible. His proof is a beautiful and unexpected reduction to the FRT tree embedding theorem. In another quite unexpected move, Raecke shows that his tree decomposition theorem can be used to obtain an O(log n)-approximation for the minimum bisection problem.
I expect that the next post, concerning the business meeting, will be a bit controversial. In other news, Adam Klivans loses $20 for betting that the desert contains papaya. It was mango.
How about some details on the outcomes of the hiring season??
ReplyDeleteSee Mihai's blog: here
ReplyDeleteThe link to "strong parallell repetition theorem" is dead.
ReplyDeleteSo I'll ask: What do you mean, it disproved a theorem (rather than conjecture)? It proved that a believed-to-be-proved theorem was actually false?
I fixed the link to the parallel repetition paper.
ReplyDeletei'll bet you another $20 that the desert contains more cactus than papaya and mango combined.
ReplyDeleteThe linked paper explains why a strong parallel repetition theorem might be important, even though now we know it's impossible. I didn't mean to imply that there is an incorrect theorem in that paper; it would be better phrased as "thereby ruling out a strong parallel repetition theorem."
ReplyDelete