Computational Complexity

Friday, February 13, 2009

 
STOC Papers

Posted by Lance

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.

5:43 AM # 1 comments

1.  Anonymous says:  
   
   Hi Lance,
   
   is the number of submitted papers
   at CCC (this year) public?
   
   I suspect that because of the unusual deadline, things may be more competitive.
   

   11:09 PM, February 13, 2009

Comment Feeds: This Post All