ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-137 | 10th March 2014 09:32

On the correlation of parity and small-depth circuits

RSS-Feed




Revision #1
Authors: Johan Hastad
Accepted on: 10th March 2014 09:32
Downloads: 805
Keywords: 


Abstract:

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



Changes to previous version:

Substantial revision of main proof.


Paper:

TR12-137 | 1st November 2012 14:45

On the correlation of parity and small-depth circuits





TR12-137
Authors: Johan Hastad
Publication: 1st November 2012 14:46
Downloads: 2088
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint