Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

DOI10.1137/S009753970138462XzbMath1029.68072MaRDI QIDQ4706215

Ran Raz, Amir Shpilka

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsmatrix productsbounded depth circuitssuperconcentrators

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle ⋮ On complexity of linear operators on the class of circuits of depth 2 ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ 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 ⋮ Expander graphs and their applications ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Min-rank conjecture for log-depth circuits ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ Lower bounds for matrix factorization ⋮ A super-quadratic lower bound for depth four arithmetic circuits

This page was built for publication: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates