New lower bounds on circuit size of multi-output functions

DOI10.1007/S00224-014-9590-4MaRDI QIDQ2354591zbMATH OpenOpenAlexFDO

Authors Evgeny Demenkov, Alexander S. Kulikov, O. Melanich, Ivan Mihajlin

Publication date 20 July 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-014-9590-4

zbMATH Keywords

lower boundsBoolean functionscircuit complexitygate elimination

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
• A lower bound on circuit complexity of vector function in \(U _{2}\)
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds

Cites work

• scientific article; zbMATH DE number 3873237 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• A Boolean function requiring 3n network size
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• Characterization of all optimal networks for a simultaneous computation of AND and NOR
• Circuit complexity and multiplicative complexity of Boolean functions
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• On the combinational complexity of certain symmetric Boolean functions
• The combinational complexity of equivalence
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(7)

• A \(5n - o(n)\) lower bound on the circuit size over \(U _{2}\) of a linear Boolean function
• Improving \(3N\) circuit complexity lower bounds
• scientific article; zbMATH DE number 4125345 (Why is no real title available?)
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• A lower bound on circuit complexity of vector function in \(U _{2}\)

This page was built for publication: New lower bounds on circuit size of multi-output functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354591)