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

DOI10.1016/j.tcs.2020.03.005zbMath1433.68141OpenAlexW3011760933MaRDI QIDQ1989349

Andrzej Lingas

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

zbMATH Keywords

Boolean circuitsBoolean circuit complexityBoolean matrix productBoolean vector convolutionsemi-disjoint bilinear form

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

Lower bounds for Boolean circuits of bounded negation width

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