Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-184 | 29th December 2014 06:59

Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

RSS-Feed




TR14-184
Authors: Ruiwen Chen, Valentine Kabanets
Publication: 29th December 2014 07:00
Downloads: 1785
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint