License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-6194
URL: http://drops.dagstuhl.de/opus/volltexte/2006/619/
Go to the corresponding Portal


Viola, Emanuele

On Probabilistic Time versus Alternating Time

pdf-format:
Document 1.pdf (306 KB)


Abstract

Sipser and Gács, and independently Lautemann, proved in '83 that probabilistic polynomial time is contained in the second level of the polynomial-time hierarchy, i.e. BPP is in Sigma_2 P. This is essentially the only non-trivial upper bound that we have on the power of probabilistic computation. More precisely, the Sipser-Gács-Lautemann simulation shows that probabilistic time can be simulated deterministically, using two quantifiers, **with a quadratic blow-up in the running time**. That is, BPTime(t) is contained in Sigma_2 Time(t^2). In this talk we discuss whether this quadratic blow-up in the running time is necessary. We show that the quadratic blow-up is indeed necessary for black-box 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 bit-string whose fraction of 1's is bounded away from 1/2 (by a constant): We show that small depth-3 circuits for approximate majority must have bottom fan-in 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 polynomial-size depth-3 circuits. This is a uniform version of a striking result by Ajtai that gives *non-uniform* polynomial-size depth-3 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 =	{1862-4405},
  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, polynomial-time hierarchy, approximate majority, constant-depth circuit}
}

Keywords: Probabilistic time, alternating time, polynomial-time hierarchy, approximate majority, constant-depth circuit
Seminar: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 30.11.2006


DROPS-Home | Fulltext Search | Imprint Published by LZI