On the complexity of monotone circuits for threshold symmetric Boolean functions

DOI10.1515/dma-2021-0031zbMath1484.94040OpenAlexW3207053979MaRDI QIDQ2064376

Igor S. Sergeev

Publication date: 5 January 2022

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2021-0031

zbMATH Keywords

complexitymonotone circuitsthreshold functionssymmetric Boolean functions

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
• New upper bounds on the Boolean circuit complexity of symmetric functions
• Sorting in \(c \log n\) parallel steps
• Extremal Combinatorics
• Bounds on Selection Networks
• Selection Networks
• On the combinational complexity of certain symmetric Boolean functions
• A Method of Constructing Selection Networks with $O(\log n)$ Depth
• A lower bound on CNF encodings of the at-most-one constraint

This page was built for publication: On the complexity of monotone circuits for threshold symmetric Boolean functions