Computational Complexity

Monday, January 03, 2005

 
Embarrassing Mistakes

Posted by Lance

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 Ran 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.

The vast majority of my papers do have, to the best of my beliefs, correct proofs. But four mistakes is enough to gain a reputation and means you should not trust my proofs on face value. I have also learned this lesson and try to get reliable people to check over my proofs before I make them public.

9:39 AM # 3 comments

1.  Anonymous says:  
   
   ... and writing "Raz Raz" instead of "Ran Raz" is
   your latest embarrassing mistake .
   

   5:26 AM, January 04, 2005

2.  Lance says:  
   
   At least that one I can fix.
   

   5:51 AM, January 04, 2005

3.  Anonymous says:  
   
   Harking back to the discussion from Dec. 28, I guess this all shows the importance of writing journal versions (at least in some cases) =)
   

   10:23 AM, January 04, 2005

Comment Feeds: This Post All