Entropy of operators or why matrix multiplication is hard for depth-two circuits

DOI10.1007/S00224-008-9133-YMaRDI QIDQ970107zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

entropybilinear formsmatrix multiplicationboolean circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical problems of computer architecture (68M07)

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; zbMATH DE number 61176
• 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

Cites work

• scientific article; zbMATH DE number 5077418 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A Lower Bound for Matrix Multiplication
• A note on matrix rigidity
• A note on the use of determinant for proving lower bounds on the size of linear circuits
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Communication in bounded depth circuits
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Linear Circuits over $\operatorname{GF}(2)$
• Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
• Lower bounds for polynomial evaluation and interpolation problems
• Lower bounds on the bounded coefficient complexity of bilinear maps
• Matrix multiplication via arithmetic progressions
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• On ACC
• On set intersection representations of graphs
• On shifting networks
• Some combinatorial-algebraic problems from complexity theory
• Superconcentrators
• Superconcentrators of depth 2
• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• The Linear Complexity of Computation

Cited in

(4)

• Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
• Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements
• The complexity of depth-two information networks
• Min-rank conjecture for log-depth circuits

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)