Thursday, June 11, 2009

The Great Oracle Debate of 1993

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.1 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?


  1. The beach resort where we had the first FCRC was so much nicer than the inland location of the last two San Diego FCRCs

2 comments:

  1. Curious Observer8:21 AM, June 12, 2009

    "So why restrict ... "

    It could be argued that well-chosen restrictions lead to more applicable results sooner. Consider physics, a science devoted to understanding a single "world" (our own).

    More general models can, in a sense, tell you more, but what if you're interested in a low grade estimation of the mass of an electron?

    Obtaining this result may be much more difficult or impossible in a more general model that describes multiple worlds.

    To solve individual problems of interest, perhaps some restrictions are warranted.

    ReplyDelete
  2. As someone getting suspiciously close to 50 (myopy sparing me the reading glasses, but I need to take off the usual ones in order to read anything), I must confess I was in the audience in San Diego 1993.

    Internet barely existed outside the USA by then. Program committees met in person with crazy traveling. And, of course, I had not even heard of some rejected paper, and I guess that, except for the PC and some close friends, and Russell and Lance and some close friends, not many people knew why on Earth a "debate about relativizations" was surprisingly announced as part of the program of FCRC'93.

    But then... "no fireworks", Lance? Kind expression... Personally I got so bored. Both Russell and Lance, kind persons as you two are, seemed to go to the longest lengths to each support *the other's* position rather than your own, if you allow me a bit of exaggeration. We came in puzzled that the debate had been scheduled, and came out even more puzzled, since we saw no reason to set up that debate. Still it is funny to try to recolect some memories now... (Old spaniards around: me hace sentir como el abuelo Cebolleta...)

    Maybe I'll read now the papers, knowing what was happening inside. (Hint for the young: my own PhD was full of oracle constructions!)

    ReplyDelete