ON THE CORRELATION OF PARITY AND SMALL-DEPTH CIRCUITS

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)).