Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication

DOI10.1137/140990280zbMath1330.68093OpenAlexW1426742690MaRDI QIDQ2949210

Srikanth Srinivasan, Nutan Limaye, Hervé Fournier, Guillaume Malod

Publication date: 8 October 2015

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

Full work available at URL: https://doi.org/10.1137/140990280

zbMATH Keywords

lower boundarithmetic circuitsdepth-four formulasiterated matrix productshifted partial derivative measure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (10)

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic circuits: the chasm at depth four gets wider
• Lower bounds and separations for constant depth multilinear circuits
• Lower bounds on arithmetic circuits via partial derivatives
• Balancing syntactically multilinear arithmetic circuits
• Characterizing Valiant's algebraic complexity classes
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Tensor-rank and lower bounds for arithmetic formulas
• Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• Arithmetic Circuits: A survey of recent results and open questions
• Parity, circuits, and the polynomial-time hierarchy
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• The limits of depth reduction for arithmetic formulas
• A super-polynomial lower bound for regular arithmetic formulas
• Separating multilinear branching programs and formulas
• Approaching the Chasm at Depth Four
• Concentration of Measure for the Analysis of Randomized Algorithms
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication