Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-175 | 26th May 2013 15:06

Randomness buys depth for approximate counting

RSS-Feed




Revision #1
Authors: Emanuele Viola
Accepted on: 26th May 2013 15:06
Downloads: 2871
Keywords: 


Abstract:

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, for every $d \ge 2$. This matches the simulation of the first type of circuits by the latter type of circuits with depth $d+2$ by Ajtai (Ann. Pure Appl. Logic; '83), and provides 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 \times A_2 \times \ldots \times A_{\lg n}$ for $A_i \subseteq [n], |A_i| = n/2$ with error $1/n$ and seed length $O(\lg n)$, improving on previous constructions for this basic setting.


Paper:

TR10-175 | 14th November 2010 19:57

Randomness buys depth for approximate counting


Abstract:

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, for every $d \ge 2$. This matches the simulation of the first type of circuits by the latter type of circuits with depth $d+2$ by Ajtai (Ann. Pure Appl. Logic; '83), and provides 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 \times A_2 \times \ldots \times A_{\lg n}$ for $A_i \subseteq [n], |A_i| = n/2$ with error $1/n$ and seed length $O(\lg n)$, improving on previous constructions for this basic setting.



ISSN 1433-8092 | Imprint