ECCC-Report TR10-175https://eccc.weizmann.ac.il/report/2010/175Comments and Revisions published for TR10-175en-usSun, 26 May 2013 15:06:41 +0300
Revision 1
| Randomness buys depth for approximate counting |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2010/175#revision1We 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.Sun, 26 May 2013 15:06:41 +0300https://eccc.weizmann.ac.il/report/2010/175#revision1
Paper TR10-175
| Randomness buys depth for approximate counting |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2010/175We 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.Sun, 14 Nov 2010 19:57:56 +0200https://eccc.weizmann.ac.il/report/2010/175