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

DOI10.1016/j.tcs.2010.12.040zbMath1217.68103OpenAlexW1949948240MaRDI QIDQ2430008

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

upper boundBoolean functionscircuit complexity

Mathematics Subject Classification ID

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

Related Items

On the limits of gate elimination ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ The simplified weighted sum function and its average sensitivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• Entropy of contact circuits and lower bounds on their complexity
• The polynomial method and restricted sums of congruence classes
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• Asymptotically Optimal Circuit for a Storage Access Function
• Cyclic Spaces for Grassmann Derivatives and Additive Theory
• Branching Programs and Binary Decision Diagrams
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• On the addition of residue classes mod p