Improving 3N circuit complexity lower bounds

Cites Work

Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
A measure \& conquer approach for the analysis of exact algorithms
Beiträge zur Störungstheorie der Spektralzerlegung
An elementary proof of a $3n - o(n)$ lower bound on the circuit complexity of affine dispersers
Title not available (Why is that?)
Cyclic Boolean circuits
Two structural results for low degree polynomials and applications
Dispersers for Affine Sources with Sub-polynomial Entropy
Circuit complexity and multiplicative complexity of Boolean functions
Method of determining lower bounds for the complexity of $\Pi$-circuits
An introduction to randomness extractors
Mining circuit lower bound proofs for meta-algorithms
A satisfiability algorithm and average-case hardness for formulas over the full binary basis
The Shrinkage Exponent of de Morgan Formulas is 2
The effect of random restrictions on formula size
Shrinkage of de Morgan formulae under restriction
Complexity theory of parallel time and hardware
A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
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
A method for obtaining more than quadratic effective lower estimates of complexity of $\pi$ schemes
Extractors for varieties
New methods for 3-SAT decision and worst-case analysis
Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
A new approach to proving upper bounds for MAX-2-SAT
Affine dispersers from subspace polynomials
On the combinational complexity of certain symmetric Boolean functions
Title not available (Why is that?)
Short PCPs with projection queries
Title not available (Why is that?)
A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
Title not available (Why is that?)
Improving exhaustive search implies superpolynomial lower bounds
Nonuniform ACC circuit lower bounds
The combinational complexity of equivalence
Lower bounds for polynomial evaluation and interpolation problems
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
Correlation bounds and \#SAT algorithms for small linear-size circuits
On the limits of gate elimination
New lower bounds on circuit size of multi-output functions
The complexity of DNF of parities
Circuit lower bounds for Merlin-Arthur classes
Title not available (Why is that?)
3.1 n − o ( n ) circuit lower bounds for explicit functions

This page was built for publication: Improving $3N$ circuit complexity lower bounds

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