License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.11
URN: urn:nbn:de:0030-drops-6194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/619/
Go to the corresponding Portal

Viola, Emanuele

On Probabilistic Time versus Alternating Time

pdf-format:
06111.ViolaEmanuele.Paper.619.pdf (0.3 MB)

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:DagSemProc.06111.11,
  author =	{Viola, Emanuele},
  title =	{{On Probabilistic Time versus Alternating Time}},
  booktitle =	{Complexity of Boolean Functions},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/619},
  URN =		{urn:nbn:de:0030-drops-6194},
  doi =		{10.4230/DagSemProc.06111.11},
  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
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 30.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI