Entropy of operators or why matrix multiplication is hard for depth-two circuits
From MaRDI portal
Publication:970107
DOI10.1007/S00224-008-9133-YzbMATH Open1209.68280OpenAlexW1982776217MaRDI QIDQ970107FDOQ970107
Authors: Stasys Jukna 
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
Recommendations
- Quantum complexity of Boolean matrix multiplication and related problems
- Entropy, stochastic matrices, and quantum operations
- Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
- scientific article
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- Relation of operator Schmidt decomposition and CNOT complexity
- On complexity of linear operators on the class of circuits of depth 2
- scientific article; zbMATH DE number 4097288
- Entropy and algorithmic complexity in quantum information theory
- A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy
Analysis of algorithms and problem complexity (68Q25) Mathematical problems of computer architecture (68M07)
Cites Work
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Title not available (Why is that?)
- Matrix multiplication via arithmetic progressions
- Linear Circuits over $\operatorname{GF}(2)$
- Lower bounds on the bounded coefficient complexity of bilinear maps
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- On set intersection representations of graphs
- Communication in bounded depth circuits
- A note on matrix rigidity
- On ACC
- A note on the use of determinant for proving lower bounds on the size of linear circuits
- The Linear Complexity of Computation
- Superconcentrators
- Boolean Circuits, Tensor Ranks, and Communication Complexity
- Some combinatorial-algebraic problems from complexity theory
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Title not available (Why is that?)
- Superconcentrators of depth 2
- Superconcentrators of depths 2 and 3; odd levels help (rarely)
- Title not available (Why is that?)
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- On shifting networks
- A Lower Bound for Matrix Multiplication
- Lower bounds for polynomial evaluation and interpolation problems
Cited In (3)
This page was built for publication: Entropy of operators or why matrix multiplication is hard for depth-two circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q970107)
