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

DOI10.1016/J.TCS.2017.11.008zbMATH Open1388.68117OpenAlexW2768675866MaRDI QIDQ1704573FDOQ1704573

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

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

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)

Cites Work

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

Cited In (11)

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

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)