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.

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.