Next: Computational Indistinguishability: A Sample
Up: Sabbatical at MIT (1996-1998)
Previous: Uniform Generation of NP-witnesses
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