Correlation bounds and \#SAT algorithms for small linear-size circuits
DOI10.1007/978-3-319-21398-9_17zbMATH Open1465.68102OpenAlexW2339207536MaRDI QIDQ3196385FDOQ3196385
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
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
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)
Cites Work
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Mining circuit lower bound proofs for meta-algorithms
- Title not available (Why is that?)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- The Shrinkage Exponent of de Morgan Formulas is 2
- Pseudorandomness from shrinkage
- Quantum lower bounds by polynomials
- Average-case lower bounds for formula size
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
- Title not available (Why is that?)
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Reflections for quantum query algorithms
- Affine extractors over prime fields
- A Boolean function requiring 3n network size
- On the construction of affine extractors
Cited In (7)
- Tighter connections between Formula-SAT and shaving logs
- On the limits of gate elimination
- Circuit size lower bounds and \#SAT upper bounds through a general framework
- Improving \(3N\) circuit complexity lower bounds
- Zero-One Designs Produce Small Hard SAT Instances
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
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)
