An n3/2 lower bound on the monotone network complexity of the Boolean convolution

DOI10.1016/S0019-9958(83)80035-7MaRDI QIDQ3698705zbMATH OpenFDO

Authors Jürgen Weiss

Publication date 1983

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

semidisjoint bilinear forms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• scientific article; zbMATH DE number 3867233
• Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
• A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
• scientific article; zbMATH DE number 176866

Cited in

(6)

• Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
• On the complexity of slice functions
• On Negations in Boolean Networks
• scientific article; zbMATH DE number 7250166 (Why is no real title available?)

This page was built for publication: An n3/2 lower bound on the monotone network complexity of the Boolean convolution

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