A well-mixed function with circuit complexity 5n: tightness of the Lachish-Raz-type bounds

DOI10.1016/J.TCS.2010.12.040MaRDI QIDQ2430008zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano, Jun Tarui

Publication date 5 April 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.12.040

zbMATH Keywords

Boolean functionscircuit complexityupper bound

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• 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
• Asymptotically Optimal Circuit for a Storage Access Function
• Branching Programs and Binary Decision Diagrams
• Cyclic Spaces for Grassmann Derivatives and Additive Theory
• Entropy of contact circuits and lower bounds on their complexity
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• scientific article; zbMATH DE number 1929951 (Why is no real title available?)
• scientific article; zbMATH DE number 1405644 (Why is no real title available?)
• scientific article; zbMATH DE number 3032896 (Why is no real title available?)
• On the addition of residue classes mod p
• The polynomial method and restricted sums of congruence classes

Cited in

(7)

• On the limits of gate elimination
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• New lower bounds on circuit size of multi-output functions
• A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
• The simplified weighted sum function and its average sensitivity
• Improving \(3N\) circuit complexity lower bounds
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024

This page was built for publication: A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds

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