Lower bounds for depth-4 formulas computing iterated matrix multiplication
From MaRDI portal
Recommendations
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- A depth-five lower bound for iterated matrix multiplication
Cites work
- A super-polynomial lower bound for regular arithmetic formulas
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Approaching the chasm at depth four
- Arithmetic circuits: a survey of recent results and open questions
- Arithmetic circuits: the chasm at depth four gets wider
- Balancing syntactically multilinear arithmetic circuits
- Characterizing Valiant's algebraic complexity classes
- Concentration of Measure for the Analysis of Randomized Algorithms
- Depth-4 lower bounds, determinantal complexity: a unified approach
- scientific article; zbMATH DE number 3744549 (Why is no real title available?)
- scientific article; zbMATH DE number 1332669 (Why is no real title available?)
- scientific article; zbMATH DE number 967945 (Why is no real title available?)
- Improved Bounds for Reduction to Depth 4 and Depth 3
- Lower bounds and separations for constant depth multilinear circuits
- Lower bounds on arithmetic circuits via partial derivatives
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- On the power of homogeneous depth 4 arithmetic circuits
- Parity, circuits, and the polynomial-time hierarchy
- Separating multilinear branching programs and formulas
- Separation of multilinear circuit and formula size
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Tensor-rank and lower bounds for arithmetic formulas
- The limits of depth reduction for arithmetic formulas
Cited in
(19)- Depth-4 lower bounds, determinantal complexity: a unified approach
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- Depth-4 lower bounds, determinantal complexity: a unified approach
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- A depth-five lower bound for iterated matrix multiplication
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- scientific article; zbMATH DE number 7009617 (Why is no real title available?)
- Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
- Barriers for rank methods in arithmetic complexity
- scientific article; zbMATH DE number 7559443 (Why is no real title available?)
- On the Symmetries of and Equivalence Test for Design Polynomials.
- A super-quadratic lower bound for depth four arithmetic circuits
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds for special cases of syntactic multilinear ABPs
- Superpolynomial lower bounds against low-depth algebraic circuits
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
This page was built for publication: Lower bounds for depth-4 formulas computing iterated matrix multiplication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949210)
