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

[Computational Complexity] The Great Oracle Debate of 1993

Expand Messages
  • Lance
    In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still
    Message 1 of 1 , Jun 11, 2009
    View Source
    • 0 Attachment
      In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still unpublished paper with Sanjeev Arora and Umesh Vazirani. Bill asked me if I knew about the controversy and I said I'd answer in a blog post.

      The Arora-Impagliazzo-Vazirani paper was submitted to the 1993 Complexity conference (then called Structure in Complexity Theory) which was part of the first FCRC conference in San Diego. The AIV paper tried to explain why the then recent interactive proof results (IP=PSPACE, MIP=NEXP, PCP theorem) don't relativize. I somehow got hold of a copy of the paper and thought AIV completely missed the mark, focusing on local checkability instead of the algebraic transformation of formulas. Also the AIV paper seemed down on relativization, a common theme, and I thought a response necessary. So I quickly wrote up my own response paper The Role of Relativization in Complexity Theory

      The PC didn't accept the AIV paper but they set up a debate between Russell and myself at the conference. Russell and I spent several wonderful hours before the debate overlooking the ocean and talking about our models [Note: The beach resort where we had the first FCRC was so much nicer than the inland location of the last two San Diego FCRCs] We did find some common ground during the day which unfortunately led to a debate without much fireworks.

      After the debate, Juris Hartmanis asked me to submit my paper to the Complexity Column he ran for the Bulletin of the EATCS and so it appeared there. AIV is still going through revisions and Russell said during the STOC talk (that's last week's STOC) that they still planned to publish it. 

      To continue the debate: Russell gave his STOC talk explaining that limiting the types of relativization would lead to "worlds" closer to our own. But you get a trade-off: While a few more techniques relativize in this model, it becomes much harder to create oracles, most of the oracles we have in the traditional model don't go through for the restricted model. Since the 1993 debate there have been many oracles in the traditional model published. Local checkability, algebraic methods and every other technique has failed to crack any of those oracles after they've been published. So why restrict our worlds when we still get so much more mileage in the traditional model?



      --
      Posted By Lance to Computational Complexity at 6/11/2009 06:03:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.