Upper bounds on the depth of symmetric Boolean functions

DOI10.3103/S0278641913040080zbMATH Open1353.94094OpenAlexW2027522969MaRDI QIDQ264012FDOQ264012

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

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

zbMATH Keywords

Boolean circuitsdepthimplementationmajority functionmultiplicationsymmetric Boolean functions

Mathematics Subject Classification ID

Boolean functions (06E30)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• On the depth complexity of the counting functions
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity and depth of formulas for symmetric Boolean functions
• Upper bounds for the size and the depth of formulae for MOD-functions

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)