Correlation bounds and \#SAT algorithms for small linear-size circuits
From MaRDI portal
Publication:344759
DOI10.1016/j.tcs.2016.05.005zbMath1353.68113MaRDI QIDQ344759
Ruiwen Chen, Valentine Kabanets
Publication date: 24 November 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.05.005
68Q25: Analysis of algorithms and problem complexity
Related Items
Gate elimination: circuit size lower bounds and \#SAT upper bounds, Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Fourier concentration from shrinkage
- 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
- Analysis of Boolean Functions
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Computational Complexity
- Quantum lower bounds by polynomials
- Average-case lower bounds for formula size
