Entropy of operators or why matrix multiplication is hard for depth-two circuits
type: Item
instance of: scholarly article
title: Entropy of operators or why matrix multiplication is hard for depth-two circuits
zbMATH Open document ID: 1209.68280
published in: Theory of Computing Systems
publication date: 2010-05-10T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68M07
zbMATH DE Number: 5706004
zbMATH Keywords: boolean circuits
zbMATH Keywords: bilinear forms
zbMATH Keywords: matrix multiplication
zbMATH Keywords: entropy
author: Stasys Jukna
MaRDI profile type: Publication
full work available at URL: s00224-008-9133-y
OpenAlex ID: W1982776217
cites work: Linear Circuits over $\operatorname{GF}(2)$
cites work: Superconcentrators of depths 2 and 3; odd levels help (rarely)
cites work: On ACC
cites work: A Lower Bound for Matrix Multiplication
cites work: Lower bounds on the bounded coefficient complexity of bilinear maps
cites work: Q3412385
cites work: Matrix multiplication via arithmetic progressions
cites work: A note on matrix rigidity
cites work: On set intersection representations of graphs
cites work: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
cites work: The Linear Complexity of Computation
cites work: Q5545524
cites work: Superconcentrators
cites work: Superconcentrators of depth 2
cites work: Communication in bounded depth circuits
cites work: A note on the use of determinant for proving lower bounds on the size of linear circuits
cites work: Some combinatorial-algebraic problems from complexity theory
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: On shifting networks
cites work: Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
cites work: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
cites work: Lower bounds for polynomial evaluation and interpolation problems
cites work: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
cites work: Q4164821
DOI: 10.1007/S00224-008-9133-Y
Recommended article: Quantum Complexity of Boolean Matrix Multiplication and Related Problems
Recommended article: Entropy, stochastic matrices, and quantum operations
Recommended article: Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
Recommended article: Q4009382
Recommended article: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
Recommended article: Relation of operator Schmidt decomposition and CNOT complexity
Recommended article: On complexity of linear operators on the class of circuits of depth 2
Recommended article: Q3824346
Recommended article: Entropy and algorithmic complexity in quantum information theory
Recommended article: Q5414631
description: scientific article; zbMATH DE number 5706004