Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
From MaRDI portal
Publication:1989349
DOI10.1016/j.tcs.2020.03.005zbMath1433.68141OpenAlexW3011760933MaRDI QIDQ1989349
Publication date: 21 April 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.03.005
Boolean circuitsBoolean circuit complexityBoolean matrix productBoolean vector convolutionsemi-disjoint bilinear form
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Negation can be exponentially powerful
- Complexity of monotone networks for Boolean matrix product
- Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
- Monotone switching circuits and Boolean matrix product
- A lower bound on the number of additions in monotone computations
- Gaussian elimination is not optimal
- Fast multiplication of large numbers
- Fast Integer Multiplication Using Modular Arithmetic
- Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Faster Integer 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
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Multiplying matrices faster than coppersmith-winograd
This page was built for publication: Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth
