Journal
SIAM JOURNAL ON COMPUTING
Volume 43, Issue 5, Pages 1699-1708Publisher
SIAM PUBLICATIONS
DOI: 10.1137/120897432
Keywords
circuits complexity; small-depth circuits; parity; switching lemma
Funding
- ERC [226 203]
Ask authors/readers for more resources
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)).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
