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

Ruiwen Chen, Valentine Kabanets

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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􀀀-n0:51, the correlation with Parity is at most 2-􀀀nΩ(1), and there is a #SAT algorithm running in time 2n-nΩ(1) ; for circuit size 2:99n, the correlation with Parity is at most 2􀀀-Ω(n), and there is a #SAT algorithm running in time 2n-Ω(n). Similar correlation bounds and algorithms are also proved for circuits of size almost 2:5n over the full binary basis B2.
Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings
PublisherSpringer International Publishing
Pages211-222
Number of pages12
ISBN (Electronic)978-3-319-21398-9
ISBN (Print)978-3-319-21397-2
DOIs
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume9198
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits'. Together they form a unique fingerprint.

Cite this