Abstract
Sipser and GÃ¡cs, and independently Lautemann, proved in '83 that probabilistic polynomial time is contained in the second level of the polynomialtime hierarchy, i.e. BPP is in Sigma_2 P. This is essentially the only nontrivial upper bound that we have on the power of probabilistic computation. More precisely, the SipserGÃ¡csLautemann simulation shows that probabilistic time can be simulated deterministically, using two quantifiers, **with a quadratic blowup in the running time**. That is, BPTime(t) is contained in Sigma_2 Time(t^2).
In this talk we discuss whether this quadratic blowup in the running time is necessary. We show that the quadratic blowup is indeed necessary for blackbox simulations that use two quantifiers, such as those of Sipser, GÃ¡cs, and Lautemann. To obtain this result, we prove a new circuit lower bound for computing **approximate majority**, i.e. computing the majority of a given bitstring whose fraction of 1's is bounded away from 1/2 (by a constant): We show that small depth3 circuits for approximate majority must have bottom fanin Omega(log n).
On the positive side, we obtain that probabilistic time can be simulated deterministically, using three quantifiers, in quasilinear time. That is, BPTime(t) is contained in Sigma_3 Time(t polylog t). Along the way, we show that approximate majority can be computed by uniform polynomialsize depth3 circuits. This is a uniform version of a striking result by Ajtai that gives *nonuniform* polynomialsize depth3 circuits for approximate majority.
If time permits, we will discuss some applications of our results to proving lower bounds on randomized Turing machines.
BibTeX  Entry
@InProceedings{viola:DSP:2006:619,
author = {Emanuele Viola},
title = {On Probabilistic Time versus Alternating Time},
booktitle = {Complexity of Boolean Functions},
year = {2006},
editor = {Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
number = {06111},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2006/619},
annote = {Keywords: Probabilistic time, alternating time, polynomialtime hierarchy, approximate majority, constantdepth circuit}
}
Keywords: 

Probabilistic time, alternating time, polynomialtime hierarchy, approximate majority, constantdepth circuit 
Seminar: 

06111  Complexity of Boolean Functions 
Issue Date: 

2006 
Date of publication: 

30.11.2006 