My Drunken Theorem

Bill's SIGACT Open Problems Column remembering Luca Trevisan is out. I chose the problem of whether Promise-ZPP in P implies Promise-BPP in P, an extension of an earlier theorem by Luca and his co-authors, which showed that Promise-RP in P implies Promise-BPP in P. But now, let me share a story that I didn’t include in print.

In the mid-1990s, I receive an email from Luca saying that Noam Nisan had told him I’d come up with an easier proof of one of his theorems. Luca asked if he could use it in his upcoming paper. I had no idea what he was talking about.

Then, I vaguely remembered…

I was in Dagstuhl, back when we’d hang out in a room meant for drinking beer and wine. I had, shall we say, more than one good German Pilsner, when Noam came by and asked if I knew how to show that Promise-RP in P implies P = BPP. I mumbled something about how it might follow from Lautemann's proof that BPP is in the second level of the polynomial-time hierarchy. Lautemann’s proof uses the probabilistic method in both directions, which I thought might fit nicely into Promise-RP.

Now to all you kids out there: you should never drink and derive. A theorem you prove after a couple of beers usually falls apart when you sober up. But this time it turns out I was right—and I totally forgot about it until I got Luca’s email.

I never admitted this to Luca but did give him permission to include it in his paper with Andreev, Clementi, and Rolim. And they did.

However, Lautemann’s proof doesn’t tell us anything about Promise-ZPP, so that problem remains open. Go ahead, read Bill’s column, and give it a try. If you drink a couple of Warsteiners along the way, it may not help you prove the theorem—but at least you’ll enjoy some good beer.