Recommendations
Cites work
- scientific article; zbMATH DE number 3916179 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 51644 (Why is no real title available?)
- scientific article; zbMATH DE number 176870 (Why is no real title available?)
- scientific article; zbMATH DE number 559220 (Why is no real title available?)
- scientific article; zbMATH DE number 1929951 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- A Boolean function requiring 3n network size
- A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
- Affine dispersers from subspace polynomials
- Algebrization: a new barrier in complexity theory
- An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Boolean function complexity. Advances and frontiers.
- Circuit size lower bounds and \#SAT upper bounds through a general framework
- Computational Complexity
- Computing all MOD-functions simultaneously
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Natural proofs
- New upper bounds on the Boolean circuit complexity of symmetric functions
- On convex complexity measures
- On the combinational complexity of certain symmetric Boolean functions
- On the limits of gate elimination
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The Shrinkage Exponent of de Morgan Formulas is 2
- The \(\text{P}=\text{NP}\) question and Gödel's lost letter
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Universal circuits (Preliminary Report)
- Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
Cited in
(5)- On the limits of gate elimination
- Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
- Gate elimination for linear functions and new feebly secure constructions
- Circuit complexity of linear functions: gate elimination and feeble security
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
This page was built for publication: On the limits of gate elimination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1635510)
