ECCC-Report TR14-184https://eccc.weizmann.ac.il/report/2014/184Comments and Revisions published for TR14-184en-usMon, 29 Dec 2014 07:00:27 +0200
Paper TR14-184
| Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits |
Ruiwen Chen,
Valentine Kabanets
https://eccc.weizmann.ac.il/report/2014/184We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there is a #SAT algorithm running in time $2^{n-n^{\Omega(1)}}$; for circuit size $2.99n$, the correlation with Parity is at most $2^{-{\Omega(n)}}$, and there is a #SAT algorithm running in time $2^{n-{\Omega(n)}}$. Similar correlation bounds and algorithms are also proved for circuits of size almost $2.5 n$ over the full binary basis $B_2$.Mon, 29 Dec 2014 07:00:27 +0200https://eccc.weizmann.ac.il/report/2014/184