ON APPROXIMATE MAJORITY AND PROBABILISTIC TIME
We prove new results on the circuit complexity of approximate majority, which is the problem of computing the majority of a given bit string whose fraction of 1's is bounded away from 1/2 (by a constant). We then apply these results to obtain new relationships between probabilistic time, BPTime (t), and alternating time, Sigma(O(1)) Time (t). Our main results are the following: 1. We prove that depth-3 circuits with bottom fan-in (log n)/2 that compute approximate majority on n bits must have size at least 2(n0.1). As a corollary we obtain that there is no black-box proof that BPTime (t) subset of Sigma(2)Time (o(t(2))). This complements the (black-box) result that BPTime (t) subset of Sigma(2)Time (t(2) . poly log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83). 2. We prove that approximate majority is computable by uniform polynomial-size circuits of depth 3. Prior to our work, the only known polynomial-size depth-3 circuits for approximate majority were non-uniform (Ajtai, Ann. Pure Appl. Logic '83). We also prove that BPTime (t) subset of Sigma(2)Time (t . poly log t). This complements our results in ( 1). 3. We prove new lower bounds for solving QSAT(3). Sigma(3)Time (n . poly log n) on probabilistic computational models. In particular, we prove that solving QSAT(3) requires time n(1+Omega(1)) on Turing machines with a random-access input tape and a sequential-access work tape that is initialized with random bits. No nontrivial lower bound was previously known on this model (for a function computable in linear space).
approximate majority probabilistic time alternating time black-box lower bound constant-depth circuit polynomial-time hierarchy quasilinear time time-space tradeoff pseudorandom generator