Breaking Walls

Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in November of 1989 that changed all that. One marked the end of the Cold War. The other marked the start of the most exciting seven weeks of my research career.

It all happened during my rookie year as an assistant professor at the University of Chicago. On November 27, 1989, Noam Nisan emailed a paper draft showing that verifying the permanent (and thus co-NP) has multiple prover interactive proofs. Besides being a major breakthrough, this was the first time someone had proven a theorem where there was a previously published oracle result that went the other way. In my very first theorem in grad school (with Mike Sipser) we had an oracle relative to which co-NP did not have single prover interactive proofs (IP). With John Rompel, we extended the result to an oracle where co-NP did not have multiple prover interactive proofs (MIP). Noam showed co-NP did have multiple prover proof systems in the non-relativized world. This led me to thinking about whether we can find a single prover proof. I worked on this problem with then student Carsten Lund and Howard Karloff who had the office across from me. After a few weeks of hacking we finally did get such a protocol. Noam agreed to merge his now weaker result into ours and we quickly wrote it up and on December 13 emailed it out to the masses (these were the days before web archives, or even a web).

It took Adi Shamir less than two weeks to find the twist to add to our proof to get the full result that IP = PSPACE that he emailed out the day after Chirstmas. Babai (jokingly I think) chastised me afterwards for going away on a planned ski trip in mid-December.

In Fortnow-Rompel-Sipser we had also showed that MIP was contained in NEXP, non-deterministisic exponential time. After IP=PSPACE I then embarked on showing that you could put all of NEXP in MIP. At one point someone asked me why I didn't first try EXP in MIP and I mumbled something about how one ought to get nondeterminism for free in this model, but deep down I didn't want another partial result that someone else could usurp. My approach (not the one anyone would teach today) involved relativizing the LFKN co-NP in IP protocol using the provers to simulate the oracle. But we needed a low-degree test to make the relativization work, and working with Carsten and Laszlo Babai, we finally came up with a proof of the test. We sent out that paper on January 17, 1990.

I remember most the breakthrough moments when Carsten walked into my office asking me why his protocol for the permanent didn't work (it did) and when Babai, Lund and I discovered that the expansion properties of the hypercube was the last piece we needed to make our linear test work.

After MIP=NEXP, I thought we now knew nearly everything that matters about interactive proofs and moved on to other areas of complexity. Thus I missed the entire PCP craze that started about a year later.

At the 1990 Structures in Complexity Conference in Barcelona, Babai gave a cool talk E-mail and the Unexpected Power of Interaction describing those then recent results and the process behind them. I used that write-up to recover the dates above.