The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
DOI10.1109/TC.1979.1675245zbMATH Open0422.68012MaRDI QIDQ3856097FDOQ3856097
Authors: Edmund A. Lamagna 
Publication date: 1979
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
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
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Discrete mathematics in relation to computer science (68R99)
Cited In (7)
- Title not available (Why is that?)
- 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)
