Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications

DOI10.1137/18M1191567zbMath1412.68069OpenAlexW2910483288MaRDI QIDQ4646460

Suryajith Chillara, Srikanth Srinivasan, Nutan Limaye

Publication date: 14 January 2019

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

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

zbMATH Keywords

lower boundsiterated matrix multiplicationalgebraic complexity theorymultilinear formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Basic linear algebra (15A99)

Related Items (5)

Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Unnamed Item ⋮ Lower bounds for special cases of syntactic multilinear ABPs ⋮ Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree ⋮ A super-quadratic lower bound for depth four arithmetic circuits

Uses Software

• lowerbounds-survey

Cites Work

• Unnamed Item
• 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
• The average sensitivity of bounded-depth formulas
• Balancing syntactically multilinear arithmetic circuits
• Improved bounds for reduction to depth 4 and depth 3
• Arithmetic Circuits: A Chasm at Depth 3
• An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
• On the Power of Homogeneous Depth 4 Arithmetic Circuits
• 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
• Probability Inequalities for Sums of Bounded Random Variables
• 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
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications