Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] STOC Papers

Expand Messages
  • Lance
    The list of accepted papers for STOC is up. Nice to see they accepted Trifonov s paper in addition to Reingold. Many other nice complexity results too. Take a
    Message 1 of 3 , Jan 25, 2005
    • 0 Attachment
      The list of accepted papers for STOC is up. Nice to see they accepted Trifonov's paper in addition to Reingold. Many other nice complexity results too. Take a look.

      --
      Posted by Lance to Computational Complexity at 1/25/2005 08:12:45 PM
    • Lance
      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
      Message 2 of 3 , Jan 31, 2006
      • 0 Attachment
        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.

        More from Suresh and PC member Scott.

        --
        Posted by Lance to Computational Complexity at 1/31/2006 09:07:00 AM

      • 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
        Message 3 of 3 , Feb 13, 2009
        • 0 Attachment
          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
        Your message has been successfully submitted and would be delivered to recipients shortly.