On the limits of gate elimination
From MaRDI portal
Publication:1635510
DOI10.1016/j.jcss.2018.04.005zbMath1393.68061OpenAlexW2804464112WikidataQ129753121 ScholiaQ129753121MaRDI QIDQ1635510
Alexander Knop, Edward A. Hirsch, Alexander S. Kulikov, Alexander Golovnev
Publication date: 6 June 2018
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2018.04.005
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- A Boolean function requiring 3n network size
- On convex complexity measures
- New upper bounds on the Boolean circuit complexity of symmetric functions
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- 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
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Weighted Gate Elimination
- Computing All MOD-Functions Simultaneously
- Algebrization
- An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
- Affine Dispersers from Subspace Polynomials
- Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- The P=NP Question and Gödel’s Lost Letter
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
- Universal circuits (Preliminary Report)
- On the combinational complexity of certain symmetric Boolean functions
- The Shrinkage Exponent of de Morgan Formulas is 2
- Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework
- On the Limits of Gate Elimination
- Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
- Computational Complexity
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Natural proofs
This page was built for publication: On the limits of gate elimination