Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution

DOI10.1007/978-3-319-55911-7_29zbMath1462.94078OpenAlexW2598290983MaRDI QIDQ2988838

Andrzej Lingas

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_29

zbMATH Keywords

Boolean vector convolutionsemi-disjoint bilinear formmonotone Boolean circuit complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (94D10)

Related Items (2)

Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• The monotone circuit complexity of Boolean functions
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• A lower bound on the number of additions in monotone computations
• Gaussian elimination is not optimal
• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• On the complexity of matrix product
• On Negations in Boolean Networks
• An n3/2 lower bound on the monotone network complexity of the Boolean convolution
• The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Shifting Graphs and Their Applications
• Multiplying matrices faster than coppersmith-winograd

This page was built for publication: Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution