Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of hamming weights 1/2 + / - Ω(1/lg d-1 n) can be solved by explicit, randomized (unbounded-fan-in) poly(n)- size depth-d circuits with error ≤ 1/3, but cannot be solved by deterministic poly(n)-size depth-(d +1) circuits, for every d ≥ 2; and the depth of both is tight. Previous results bounded the depth to within at least an additive 2. Our sharper bounds match Ajtai's simulation of randomized depth-d circuits by deterministic depth-(d+2) circuits (Ann. Pure Appl. Logic; ' 83), and provide an example where randomization (provably) buys resources. Techniques: To rule out deterministic circuits we combine the switching lemma with an earlier depth-3 lower bound by the author (Comp. Complexity 2009). To exhibit randomized circuits we combine recent analyses by Amano (ICALP '09) and Brody and Verbin (FOCS '10) with derandomization. To make these circuits explicit which we find important for the main message of this paper we construct a new pseudorandom generator for certain combinatorial rectangle tests. Based on expander walks, the generator for example fools tests A 1 × A 2 ×. .. × A lg n for A i ⊆ [n], |A i | = n/2 with error 1/n and seed length O(lg n), improving on the seed length Ω(lg n lg lg n) of previous constructions.

Authors

• Emanuele Viola

Keywords

• Generators
• Integrated circuit modeling
• Hamming weight
• Approximation methods
• Upper bound
• Logic gates
• Graph theory
• Deterministic
• Lower Bound
• Random Walk
• Largest Eigenvalue
• Random Input
• Random Bits
• Input Bits
• Family Of Graphs
• small-depth circuit
• randomness vs. determinism
• depth
• approximate counting
• approximate majority
• pseudorandom generator
• combinatorial rectangle