On the limits of gate elimination

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

zbMATH Keywords

lower boundscircuit complexitygate elimination

Mathematics Subject Classification ID

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