A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions

DOI10.1137/0220032zbMath0734.68041OpenAlexW2035917269MaRDI QIDQ3361881

Uri Zwick

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220032

zbMATH Keywords

Boolean functionslower boundcombinational complexity

Mathematics Subject Classification ID

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

Related Items

Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ 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 ⋮ On the power of nondeterministic circuits and co-nondeterministic circuits ⋮ Reductions for monotone Boolean circuits ⋮ New upper bounds on the Boolean circuit complexity of symmetric functions ⋮ On Negations in Boolean Networks ⋮ New lower bounds on circuit size of multi-output functions