[Computational Complexity] Embarrassing Mistakes
We talked about embarrassing moments in our careers recently. I've had talks gone bad and conversations with person A thinking they were person B. And once I had a little too much sake in Tokyo and I … never mind.
But alas my biggest embarrassments were the serious problems with published proofs in several of my early papers. So to start out the New Year with a clean slate I will list my failings. Don't blame my co-authors; I take full responsibility for all these mistakes.
- In my first major paper, The Complexity of Perfect Zero-Knowledge, I showed some properties of zero-knowledge proofs using the coins of a verifier. Turns out that doesn't work as I thought. Aiello and Håstad give a correct proof and new results using the coins of the simulator. See the appendix of Goldreich-Ostrovsky-Petrank for more details.
- In the conference version of the paper On
the power of multi-power interactive protocols
we had to reduce to
error of a multi-prover proof system and wrote
We can run the protocol in parallel without any problem since all messages are independent coin tosses.Actually correct as long as you interpret "without any problem " as an forty-page proof by Raz Raz. Section 6 of our journal version describes the problem and some earlier fixes.
- The paper Probabilistic Computation and Linear Time simply had a bad proof of the main result giving a relativized world where BPP was in BPTIME(n). Berg and Håstad discuss the issue. Rettinger and Verbeek have a purported proof of the non-adaptive case and Rettinger claims to have solved the general version in his thesis (in German).
- In the FOCS paper Using Autoreducibility to Separate Complexity Classes we claimed that all the EXPSPACE complete sets were autoreducible. We later realized this result would separate NP from L and discovered the FOCS paper had a bad proof. The autoreducibility of EXPSPACE remains open and settling it in either direction would have major complexity consequences. The journal version has more details.
Posted by Lance to Computational Complexity at 1/3/2005 09:39:23 AM