next up previous
Next: Computational Indistinguishability: A Sample Up: Sabbatical at MIT (1996-1998) Previous: Uniform Generation of NP-witnesses

Another proof that BPP subseteq PH (and more)

This work provides another proof of the Sipser-Lautemann Theorem by which BPP is contained in MA (which in turn is in PH). The current proof is based on known results regarding the amplification of BPP (or ``error reduction''). Given these strong results, the current proof is even simpler than previous ones.


Comments: Authored by O. Goldreich and D. Zuckerman. Appeared in

ECCC, TR97-045, 1997.



Oded Goldreich
2003-07-30