Gate elimination: circuit size lower bounds and \#SAT upper bounds

DOI10.1016/j.tcs.2017.11.008zbMath1388.68117OpenAlexW2768675866MaRDI QIDQ1704573

Alexander Golovnev, Suguru Tamaki, Alexander S. Kulikov, Alexander V. Smal

Publication date: 12 March 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.11.008

zbMATH Keywords

lower boundssatisfiabilitycircuit complexityexponential time algorithms

Mathematics Subject Classification ID

Related Items (2)

Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Projection heuristics for binary branchings between sum and product

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Extractors and rank extractors for polynomial sources
• Arthur and Merlin as oracles
• Affine extractors over prime fields
• A Boolean function requiring 3n network size
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Exponential lower bounds for depth three Boolean circuits
• Extractors for varieties
• Mining circuit lower bound proofs for meta-algorithms
• New lower bounds on circuit size of multi-output functions
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
• The Complexity of DNF of Parities
• Weighted Gate Elimination
• Natural Proofs versus Derandomization
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
• An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
• Affine Dispersers from Subspace Polynomials
• Nonuniform ACC Circuit Lower Bounds
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• Local Reductions
• A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• Circuit Lower Bounds for Merlin–Arthur Classes
• Circuit Complexity and Multiplicative Complexity of Boolean Functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions
• Beating Brute Force for Systems of Polynomial Equations over Finite Fields
• Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
• On the Limits of Gate Elimination
• Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
• New algorithms and lower bounds for circuits with linear threshold gates
• Short PCPs with Projection Queries
• On the Correlation of Parity and Small-Depth Circuits
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Oblivious Symmetric Alternation
• Dispersers for Affine Sources with Sub-polynomial Entropy
• Average-case lower bounds for formula size

This page was built for publication: Gate elimination: circuit size lower bounds and \#SAT upper bounds