Improving 3N circuit complexity lower bounds
From MaRDI portal
Cites work
- 3.1 n − o ( n ) circuit lower bounds for explicit functions
- 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 measure \& conquer approach for the analysis of exact algorithms
- A method for obtaining more than quadratic effective lower estimates of complexity of schemes
- A new approach to proving upper bounds for MAX-2-SAT
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- 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 introduction to randomness extractors
- Beiträge zur Störungstheorie der Spektralzerlegung
- Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
- Circuit complexity and multiplicative complexity of Boolean functions
- Circuit lower bounds for Merlin-Arthur classes
- Complexity theory of parallel time and hardware
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Cyclic Boolean circuits
- Dispersers for Affine Sources with Sub-polynomial Entropy
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
- Extractors for varieties
- scientific article; zbMATH DE number 1335875 (Why is no real title available?)
- scientific article; zbMATH DE number 1178976 (Why is no real title available?)
- scientific article; zbMATH DE number 1929951 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- scientific article; zbMATH DE number 3285250 (Why is no real title available?)
- Improving exhaustive search implies superpolynomial lower bounds
- Lower bounds for polynomial evaluation and interpolation problems
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Mining circuit lower bound proofs for meta-algorithms
- New lower bounds on circuit size of multi-output functions
- New methods for 3-SAT decision and worst-case analysis
- Nonuniform ACC circuit lower bounds
- On the combinational complexity of certain symmetric Boolean functions
- On the limits of gate elimination
- Short PCPs with projection queries
- Shrinkage of de Morgan formulae under restriction
- The combinational complexity of equivalence
- The complexity of DNF of parities
- The effect of random restrictions on formula size
- The Shrinkage Exponent of de Morgan Formulas is 2
- Two structural results for low degree polynomials and applications
- Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
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)
