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

DOI10.1007/978-3-319-21398-9_17MaRDI QIDQ3196385zbMATH OpenOpenAlexFDO

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

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

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

• 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
• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• 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

(8)

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

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)