Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-045 | 29th September 1997 00:00

#### Another proof that BPP subseteq PH (and more).

TR97-045
Authors: Oded Goldreich, David Zuckerman
Publication: 1st October 1997 14:53
Keywords:

Abstract:

We provide another proof of the Sipser--Lautemann Theorem
by which \$BPP\subseteq MA\$ (\$\subseteq PH\$).
The current proof is based on strong
results regarding the amplification of \$BPP\$, due to Zuckerman.
Given these results, the current proof is even simpler than previous ones.
Furthermore, extending the proof leads to two results regarding \$MA\$:
\$MA\subseteq ZPP^NP\$ (which seems to be new),
and that two-sided error \$MA\$ equals \$MA\$.
Finally, we survey the known facts regarding the fragment of
the polynomial-time hierarchy which contains \$MA\$.

### Comment(s):

Comment #1 to TR97-045 | 16th June 1998 14:34

#### Comment Comment on: TR97-045

Comment #1
Authors: Peter Bro Miltersen
Accepted on: 16th June 1998 14:34