Improving \(3N\) circuit complexity lower bounds
From MaRDI portal
Publication:6184294
DOI10.1007/s00037-023-00246-9MaRDI QIDQ6184294
Alexander Golovnev, Magnus Gausdal Find, Alexander S. Kulikov, Edward A. Hirsch
Publication date: 24 January 2024
Published in: Computational Complexity (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Cyclic Boolean 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
- Complexity theory of parallel time and hardware
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- The combinational complexity of equivalence
- Lower bounds for polynomial evaluation and interpolation problems
- Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
- Extractors for varieties
- New methods for 3-SAT decision and worst-case analysis
- Mining circuit lower bound proofs for meta-algorithms
- New lower bounds on circuit size of multi-output functions
- A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Beiträge zur Störungstheorie der Spektralzerlegung
- The Complexity of DNF of Parities
- Weighted Gate Elimination
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- An Introduction to Randomness Extractors
- An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
- Nonuniform ACC Circuit Lower Bounds
- Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
- A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
- A measure & conquer approach for the analysis of exact algorithms
- Circuit Lower Bounds for Merlin–Arthur Classes
- Circuit Complexity and Multiplicative Complexity of Boolean Functions
- A new approach to proving upper bounds for MAX-2-SAT
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- On the combinational complexity of certain symmetric Boolean functions
- The Shrinkage Exponent of de Morgan Formulas is 2
- On the Limits of Gate Elimination
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Short PCPs with Projection Queries
- Affine dispersers from subspace polynomials
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Dispersers for Affine Sources with Sub-polynomial Entropy
- 3.1 n − o ( n ) circuit lower bounds for explicit functions
This page was built for publication: Improving \(3N\) circuit complexity lower bounds
