[Computational Complexity] STOC Papers
The accepted papers of STOC have been posted. A few on the list I have mentioned before including Daskalakis, Goldberg and Papadimitriou on Computing the Nash Equilibrium (see also this extension that appeared after the STOC deadline), the Kelner-Spielman and Guruswami-Rudra papers and of course Irit Dinur's new proof of the PCP theorem, surely a lock for best paper.
There are several other interesting looking papers, including Zuckerman's Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Ambainis, Spalek and de Wolf on Quantum Direct Product Theorems and Charikar, Makarychev and Makarychev with Near-Optimal Algorithms for Unique Games. I can't find the latter online but here is the result from a talk abstract.
We present new approximation algorithms for unique games that satisfy roughly k-ε/2 and 1 - O((ε log k)1/2) fraction of all constraints if 1 - ε fraction of all constraints is satisfiable. These results show limitations on the hardness bounds achievable using UGC. In particular, they disprove a stronger version of UGC that was conjectured in a recent paper. Somewhat surprisingly, even a slight improvement of our results (beyond low order terms) will disprove the unique games conjecture.Many more interesting papers, be sure to look the list over yourself.
- Last reminder: Complexity submission deadline tonight midnight Eastern.
In a nice move, Mitzenmacher posted both the titles and abstracts of STOC papers on the STOC website. Lots of strong papers, of course. Here are some that interest me for various selfish reasons.
- Exact Learning of Random DNF Formulas Under the Uniform Distribution by Linda Sellie. Linda was one of my first students at Chicago when I first started there in the late 80's but she had to leave graduate school early. But eventually she came back, kept working and received her Ph.D. from U. Chicago last spring under Stuart Kurtz with a thesis based on this nice learning result.
- An Axiomatic Approach to Algebrization by Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova. I like oracle results. I also like meta-oracle results. But especially I like meta-oracle results that generalize my meta-oracle results.
- A constructive proof of the Lovász Local Lemma by Robin Moser. The Lovász Local Lemma is a neat theorem that says if you have k events each occuring with probability p such that each event is independent of all but d other events than there is a positive probility that none of the events occur if ep(d+1)≤1 (no k in formula). Looks like Moser has a strong constructive proof. Alas while I like the Lemma, I never seem to have the right independence requirements whenever I want to use it.
Posted By Lance to Computational Complexity at 2/13/2009 05:43:00 AM