On the complexity of monotone circuits for threshold symmetric Boolean functions

DOI10.1515/DMA-2021-0031MaRDI QIDQ2064376zbMATH OpenOpenAlexFDO

Authors I. 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 circuitssymmetric Boolean functionsthreshold functions

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4211970
• scientific article; zbMATH DE number 4217938
• scientific article; zbMATH DE number 3906395
• The complexity of computing symmetric functions using threshold circuits
• About complexity of implementing threshold functions

Cites work

• A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
• A Method of Constructing Selection Networks with O(\log n) Depth
• Bounds on Selection Networks
• Extremal combinatorics. With applications in computer science
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 42045 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 3251434 (Why is no real title available?)
• scientific article; zbMATH DE number 3285250 (Why is no real title available?)
• New upper bounds on the Boolean circuit complexity of symmetric functions
• On the combinational complexity of certain symmetric Boolean functions
• Selection Networks
• Sorting in \(c \log n\) parallel steps

Cited in

(17)

• Efficient monotone circuits for threshold functions
• The complexity of computing symmetric functions using threshold circuits
• Simplified Reed-Muller expressions for residue threshold functions
• The conjunction complexity asymptotic of self-correcting circuits for monotone symmetric functions with threshold 2
• On complexity of realisation of a class of almost symmetric functions by formulas of depth 3
• scientific article; zbMATH DE number 4217938 (Why is no real title available?)
• Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
• scientific article; zbMATH DE number 3906395 (Why is no real title available?)
• scientific article; zbMATH DE number 4049560 (Why is no real title available?)
• scientific article; zbMATH DE number 609922 (Why is no real title available?)
• scientific article; zbMATH DE number 774000 (Why is no real title available?)
• scientific article; zbMATH DE number 919269 (Why is no real title available?)
• ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS
• About complexity of implementing threshold functions
• A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
• Comment on Kochol's paper ``Efficient monotone circuits for threshold functions
• Reductions for monotone Boolean circuits

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

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