On Approximate Majority and Probabilistic Time
Emanuele Viola · Proceedings - IEEE Conference on Computational Complexity/Proceedings · 2007
We prove new results on the circuit complexity of approximate majority, which is the problem of computing 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, SigmaO(1)Time (t).