Efficient monotone circuits for threshold functions

DOI10.1016/0020-0190(89)90011-2MaRDI QIDQ1122560zbMATH OpenOpenAlexFDO

Authors Martin Kochol

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0020-0190(89)90011-2

zbMATH Keywords

Boolean functionthreshold functioncircuit complexitymonotone circuitsorting network

Mathematics Subject Classification ID

Recommendations

• Monotone circuits for monotone weighted threshold functions
• Threshold functions and bounded depth monotone circuits
• On the complexity of monotone circuits for threshold symmetric Boolean functions
• Comment on Kochol's paper ``Efficient monotone circuits for threshold functions
• scientific article; zbMATH DE number 4217938
• scientific article; zbMATH DE number 609922
• The monotone circuit complexity of Boolean functions
• Design of logic circuits by approximating monotone functions
• scientific article; zbMATH DE number 773998
• Approximating threshold circuits by rational functions

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3194094 (Why is no real title available?)
• An Improved Lower Bound for Sorting Networks
• Bounds to Complexities of Networks for Sorting and for Switching
• Shifting Graphs and Their Applications
• Sorting in \(c \log n\) parallel steps

Cited in

(13)

• Reductions for Monotone Boolean Circuits
• Threshold functions and bounded depth monotone circuits
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
• Monotone circuits for matching require linear depth
• scientific article; zbMATH DE number 3906395 (Why is no real title available?)
• Directed monotone contact networks for threshold functions
• Lower bounds for Boolean circuits of bounded negation width
• scientific article; zbMATH DE number 609922 (Why is no real title available?)
• Monotone Circuits for the Majority Function
• scientific article; zbMATH DE number 4217938 (Why is no real title available?)
• Comment on Kochol's paper ``Efficient monotone circuits for threshold functions
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Monotone circuits for monotone weighted threshold functions

This page was built for publication: Efficient monotone circuits for threshold functions

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