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

DOI10.1016/J.TCS.2017.11.008MaRDI QIDQ1704573zbMATH OpenOpenAlexFDO

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

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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Circuit size lower bounds and \#SAT upper bounds through a general framework
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• On the limits of gate elimination
• On the limits of gate elimination

Cites work

• scientific article; zbMATH DE number 3618783 (Why is no real title available?)
• scientific article; zbMATH DE number 1335875 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• 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 moderately exponential time algorithm for \(k\)-IBDD satisfiability
• A nonuniform circuit class with multilayer of threshold gates having super quasi polynomial size lower bounds against NEXP
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• Affine dispersers from subspace polynomials
• 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
• Arthur and Merlin as oracles
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Average-case lower bounds for formula size
• Beating brute force for systems of polynomial equations over finite fields
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Circuit complexity and multiplicative complexity of Boolean functions
• Circuit lower bounds for Merlin-Arthur classes
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Dispersers for Affine Sources with Sub-polynomial Entropy
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Exponential lower bounds for depth three Boolean circuits
• Extractors and rank extractors for polynomial sources
• Extractors for polynomial sources over fields of constant order and small characteristic
• Extractors for varieties
• Improved algorithms for sparse MAX-SAT and MAX-\(k\)-CSP
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Improving exhaustive search implies superpolynomial lower bounds
• Ironic complicity: satisfiability algorithms and circuit lower bounds
• Local reductions
• Mining circuit lower bound proofs for meta-algorithms
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of \(o(\log \log n)\) depth
• New lower bounds on circuit size of multi-output functions
• Nonuniform ACC circuit lower bounds
• Oblivious Symmetric Alternation
• On the Correlation of Parity and Small-Depth Circuits
• On the combinational complexity of certain symmetric Boolean functions
• On the limits of gate elimination
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
• Short PCPs with projection queries
• The complexity of DNF of parities
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(11)

• On the limits of gate elimination
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• On the limits of gate elimination
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Projection heuristics for binary branchings between sum and product
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size
• On the limit of some algorithmic approach to circuit lower bounds
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704573)