Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
From MaRDI portal
Recommendations
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- A depth-five lower bound for iterated matrix multiplication
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
Cites work
- A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Amplifying lower bounds by means of self-reducibility
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Arithmetic circuits: a chasm at depth 3
- Arithmetic circuits: a survey of recent results and open questions
- Balancing syntactically multilinear arithmetic circuits
- Concentration of Measure for the Analysis of Randomized Algorithms
- Fast Parallel Computation of Polynomials Using Few Processors
- Homogeneous formulas and symmetric polynomials
- scientific article; zbMATH DE number 7250151 (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 for depth 4 formulas computing iterated matrix multiplication
- Lower bounds on arithmetic circuits via partial derivatives
- On the power of homogeneous depth 4 arithmetic circuits
- On the size of homogeneous and of depth four formulas with low individual degree
- Probability Inequalities for Sums of Bounded Random Variables
- Separating multilinear branching programs and formulas
- Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits
- Separation of \(\mathrm{AC}^0[\oplus]\) formulas and circuits
- Separation of multilinear circuit and formula size
- Tensor-rank and lower bounds for arithmetic formulas
- The average sensitivity of bounded-depth formulas
- The Parallel Evaluation of General Arithmetic Expressions
Cited in
(11)- Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
- Slightly improved lower bounds for homogeneous formulas of bounded depth and bounded individual degree
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
- A depth-five lower bound for iterated matrix multiplication
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- scientific article; zbMATH DE number 7559443 (Why is no real title available?)
- A super-quadratic lower bound for depth four arithmetic circuits
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- Lower bounds for special cases of syntactic multilinear ABPs
- Improved lower bound, and proof barrier, for constant depth algebraic circuits
This page was built for publication: Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4646460)
