New upper bounds on the Boolean circuit complexity of symmetric functions

DOI10.1016/j.ipl.2010.01.007zbMath1209.68274OpenAlexW2009341260MaRDI QIDQ991778

Grigory Yaroslavtsev, Alexander S. Kulikov, Arist Kojevnikov, Evgeny Demenkov

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.01.007

zbMATH Keywords

computational complexityupper boundsmodular functionssymmetric functionsBoolean circuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Upper bounds on the depth of symmetric Boolean functions ⋮ Application of Grover's algorithm to check non-resiliency of a Boolean function ⋮ On the limits of gate elimination ⋮ Complexity of computation in finite fields ⋮ Upper bounds for the formula size of symmetric Boolean functions ⋮ Efficient quantum algorithms to construct arbitrary Dicke states ⋮ On the complexity of monotone circuits for threshold symmetric Boolean functions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• A Boolean function requiring 3n network size
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions

This page was built for publication: New upper bounds on the Boolean circuit complexity of symmetric functions