On the limits of gate elimination

DOI10.1016/J.JCSS.2018.04.005zbMATH Open1393.68061OpenAlexW2804464112WikidataQ129753121 ScholiaQ129753121MaRDI QIDQ1635510FDOQ1635510

Authors: Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov 

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

Recommendations

• On the limits of gate elimination
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• scientific article; zbMATH DE number 1256716
• scientific article; zbMATH DE number 176870
• scientific article; zbMATH DE number 4049557

zbMATH Keywords

lower boundscircuit complexitygate elimination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Computational Complexity
• Title not available (Why is that?)
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Applications of matrix methods to the theory of lower bounds in computational complexity
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• Boolean function complexity. Advances and frontiers.
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• The Shrinkage Exponent of de Morgan Formulas is 2
• Algebrization: a new barrier in complexity theory
• Title not available (Why is that?)
• A Boolean function requiring 3n network size
• Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
• Title not available (Why is that?)
• On convex complexity measures
• On the combinational complexity of certain symmetric Boolean functions
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The \(\text{P}=\text{NP}\) question and Gödel's lost letter
• Title not available (Why is that?)
• Natural proofs
• Title not available (Why is that?)
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Affine dispersers from subspace polynomials
• Circuit size lower bounds and \#SAT upper bounds through a general framework
• Title not available (Why is that?)
• Universal circuits (Preliminary Report)
• Title not available (Why is that?)
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds
• Computing all MOD-functions simultaneously
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• On the limits of gate elimination
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

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)