Improving 3N circuit complexity lower bounds
From MaRDI portal
(Redirected from Improving 3N circuit complexity lower bounds)
Improving \(3N\) circuit complexity lower bounds
Improving \(3N\) circuit complexity lower bounds
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)
