We prove that the correlation of a depth-d
unbounded fanin circuit of size S with parity
of n variables is at most 2^{-\Omega(n/(\log S)^{d-1})}.
Substantial revision of main proof.
We prove that the correlation of a depth-d
unbounded fanin circuit of size S with parity
of n variables is at most 2^{-\Omega(n/(\log S)^{d-1})}.