Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We show that the promise problem of distinguishing $n$-bit strings of hamming weights $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$; 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. \bigskip \emph{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 the seed length $\Omega(\lg n \lg \lg n)$ of previous constructions.

Questions and Answers

You need to be logged in to be able to post here.