Gate elimination: circuit size lower bounds and \#SAT upper bounds
type: Item
instance of: scholarly article
title: Gate elimination: circuit size lower bounds and \#SAT upper bounds
zbMATH Open document ID: 1388.68117
author: Alexander Golovnev
author: Alexander S. Kulikov
author: Alexander V. Smal
author: Suguru Tamaki
published in: Theoretical Computer Science
publication date: 2018-03-12T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6848999
zbMATH Keywords: circuit complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: exponential time algorithms
zbMATH Keywords: satisfiability
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.11.008
OpenAlex ID: W2768675866
cites work: A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP
cites work: A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
cites work: Q3191591
cites work: Affine Dispersers from Subspace Polynomials
cites work: Short PCPs with Projection Queries
cites work: A Boolean function requiring 3n network size
cites work: Q4258566
cites work: Oblivious Symmetric Alternation
cites work: Arthur and Merlin as oracles
cites work: Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
cites work: Correlation bounds and \#SAT algorithms for small linear-size circuits
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: An improved deterministic \#SAT algorithm for small De Morgan formulas
cites work: Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
cites work: Average-case lower bounds and satisfiability algorithms for small threshold circuits
cites work: The complexity of DNF of parities
cites work: An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
cites work: New lower bounds on circuit size of multi-output functions
cites work: Extractors for varieties
cites work: Extractors and rank extractors for polynomial sources
cites work: On the Limits of Gate Elimination
cites work: Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
cites work: Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
cites work: On the Correlation of Parity and Small-Depth Circuits
cites work: Q5743451
cites work: Q4708583
cites work: Local Reductions
cites work: Circuit Complexity and Multiplicative Complexity of Boolean Functions
cites work: Average-case lower bounds for formula size
cites work: Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
cites work: Q5503674
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: Beating Brute Force for Systems of Polynomial Equations over Finite Fields
cites work: Q4183227
cites work: A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
cites work: Exponential lower bounds for depth three Boolean circuits
cites work: A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
cites work: Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression
cites work: Circuit Lower Bounds for Merlin–Arthur Classes
cites work: Q4904160
cites work: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
cites work: A satisfiability algorithm and average-case hardness for formulas over the full binary basis
cites work: Dispersers for Affine Sources with Sub-polynomial Entropy
cites work: On the combinational complexity of certain symmetric Boolean functions
cites work: NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
cites work: Improving exhaustive search implies superpolynomial lower bounds
cites work: New algorithms and lower bounds for circuits with linear threshold gates
cites work: Nonuniform ACC Circuit Lower Bounds
cites work: Natural proofs versus derandomization
cites work: Affine extractors over prime fields
cites work: A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
DOI: 10.1016/J.TCS.2017.11.008
description: scientific article; zbMATH DE number 6848999