Upper bounds on the depth of symmetric Boolean functions

DOI10.3103/S0278641913040080MaRDI QIDQ264012zbMATH OpenOpenAlexFDO

Authors I. S. Sergeev

Publication date 5 April 2016

Published in Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s0278641913040080

zbMATH Keywords

Boolean circuitsdepthimplementationmajority functionmultiplicationsymmetric Boolean functions

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• Complexity and depth of formulas for symmetric Boolean functions
• Upper bounds for the formula size of symmetric Boolean functions
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Upper bounds on the multiplicative complexity of symmetric Boolean functions
• Bounded-depth, polynomial-size circuits for symmetric functions

Cites work

• New upper bounds on the Boolean circuit complexity of symmetric functions
• Shallow circuits and concise formulae for multiple addition and multiplication

Cited in

(9)

• scientific article; zbMATH DE number 2237377 (Why is no real title available?)
• On the depth complexity of the counting functions
• Sharpening an upper bound on the adder and comparator depths
• New upper bounds on the Boolean circuit complexity of symmetric functions
• scientific article; zbMATH DE number 1285633 (Why is no real title available?)
• Complexity and depth of formulas for symmetric Boolean functions
• Upper bounds for the formula size of symmetric Boolean functions
• Upper bounds for the size and the depth of formulae for MOD-functions
• Multiplication

This page was built for publication: Upper bounds on the depth of symmetric Boolean functions

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