Correlation bounds and \#SAT algorithms for small linear-size circuits

DOI10.1007/978-3-319-21398-9_17MaRDI QIDQ3196385zbMATHOpenAlexFDO

Authors 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)

Recommendations

• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• Average-case lower bounds and satisfiability algorithms for small threshold circuits

Cites work

• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• A Boolean function requiring 3n network size
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• Affine extractors over prime fields
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Average-case lower bounds for formula size
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Mining circuit lower bound proofs for meta-algorithms
• On the construction of affine extractors
• Pseudorandomness from shrinkage
• Quantum lower bounds by polynomials
• Reflections for quantum query algorithms
• The Shrinkage Exponent of de Morgan Formulas is 2
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(7)

• On the limits of gate elimination
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• Improving \(3N\) circuit complexity lower bounds
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Zero-One Designs Produce Small Hard SAT Instances
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Tighter connections between Formula-SAT and shaving logs

This page was built for publication: Correlation bounds and \#SAT algorithms for small linear-size circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196385)