New lower bounds on circuit size of multi-output functions

DOI10.1007/S00224-014-9590-4zbMATH Open1331.68084OpenAlexW2084301310MaRDI QIDQ2354591FDOQ2354591

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

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

zbMATH Keywords

lower boundsBoolean functionscircuit complexitygate elimination

Mathematics Subject Classification ID

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

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• An elementary proof of a \(3n - o(n)\) lower bound on the circuit complexity of affine dispersers
• Circuit complexity and multiplicative 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
• Title not available (Why is that?)
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• A Boolean function requiring 3n network size
• Title not available (Why is that?)
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• On the combinational complexity of certain symmetric Boolean functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• The combinational complexity of equivalence
• Characterization of all optimal networks for a simultaneous computation of AND and NOR

Cited In (5)

• Title not available (Why is that?)
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• Improving \(3N\) circuit complexity lower 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

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)