Entropy of operators or why matrix multiplication is hard for depth-two circuits
From MaRDI portal
Publication:970107
DOI10.1007/s00224-008-9133-yzbMath1209.68280MaRDI QIDQ970107
Publication date: 10 May 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-008-9133-y
68Q25: Analysis of algorithms and problem complexity
68M07: Mathematical problems of computer architecture
Related Items
Min-rank conjecture for log-depth circuits, Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements, Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
Cites Work
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- A note on matrix rigidity
- On shifting networks
- Matrix multiplication via arithmetic progressions
- Superconcentrators of depth 2
- Superconcentrators of depths 2 and 3; odd levels help (rarely)
- Communication in bounded depth circuits
- Some combinatorial-algebraic problems from complexity theory
- On ACC
- Lower bounds for polynomial evaluation and interpolation problems
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Linear Circuits over $\operatorname{GF}(2)$
- Lower bounds on the bounded coefficient complexity of bilinear maps
- On set intersection representations of graphs
- The Linear Complexity of Computation
- Superconcentrators
- A Lower Bound for Matrix Multiplication
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- Unnamed Item
- Unnamed Item
- Unnamed Item
