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

DOI10.1109/TC.1979.1675245zbMath0422.68012MaRDI QIDQ3856097

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)

Related Items

On the complexity of 2-output Boolean networks, Boolean functions whose monotone complexity is of size \(n^ 2\) / log n, Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Reductions for monotone Boolean circuits, Unnamed Item, On Negations in Boolean Networks