Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
DOI10.4230/LIPIcs.STACS.2018.21zbMath1487.68119arXiv1710.05481OpenAlexW2964040447MaRDI QIDQ3304115
Suryajith Chillara, Srikanth Srinivasan, Nutan Limaye
Publication date: 5 August 2020
Full work available at URL: https://arxiv.org/abs/1710.05481
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) Basic linear algebra (15A99) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (3)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Lower bounds and separations for constant depth multilinear circuits
- Homogeneous formulas and symmetric polynomials
- Lower bounds on arithmetic circuits via partial derivatives
- Balancing syntactically multilinear arithmetic circuits
- Improved bounds for reduction to depth 4 and depth 3
- Arithmetic Circuits: A Chasm at Depth 3
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- Amplifying lower bounds by means of self-reducibility
- The Parallel Evaluation of General Arithmetic Expressions
- Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- On the size of homogeneous and of depth four formulas with low individual degree
- Tensor-Rank and Lower Bounds for Arithmetic Formulas
- Separating multilinear branching programs and formulas
This page was built for publication: Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
