The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging

DOI10.1109/TC.1979.1675245MaRDI QIDQ3856097zbMATH OpenFDO

Authors Edmund A. Lamagna

Publication date 1979

Published in IEEE Transactions on Computers (Search for Journal in Brave)

zbMATH Keywords

mergingBoolean convolutionrouting networkscombinational complexitycombinational switching networkscyclic and logical shiftinglower bounds on the size of monotone switching circuits for certain bilinear formsmonotone switching networkssynthesize monotone Boolean functionsToeplitz and circulant matrix-vector products

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Discrete mathematics in relation to computer science (68R99)

Cited in

(7)

• scientific article; zbMATH DE number 7250166 (Why is no real title available?)
• Reductions for monotone Boolean circuits
• Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
• On Negations in Boolean Networks
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• On the complexity of 2-output Boolean networks
• Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution

This page was built for publication: The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging

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