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

DOI10.1007/978-3-319-21398-9_17zbMath1465.68102OpenAlexW2339207536MaRDI QIDQ3196385

Ruiwen Chen, Valentine Kabanets

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/20054840/Chen_COCOON15.pdf

zbMATH Keywords

Boolean circuitcorrelation boundrandom restrictionsatisfiability algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06) Computational aspects of satisfiability (68R07)

Related Items (3)

On the limits of gate elimination ⋮ Unnamed Item ⋮ Improving \(3N\) circuit complexity lower bounds

Cites Work

• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Affine extractors over prime fields
• A Boolean function requiring 3n network size
• On the construction of affine extractors
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Mining circuit lower bound proofs for meta-algorithms
• An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
• An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• The Shrinkage Exponent of de Morgan Formulas is 2
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Pseudorandomness from Shrinkage
• Quantum lower bounds by polynomials
• Average-case lower bounds for formula size
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits