Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
From MaRDI portal
Publication:3196385
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
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits