Lower bounds for depth 4 formulas computing iterated matrix multiplication
Authors:
Open Access
- 31 May 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 128-135
Abstract
We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas. We also study ΣΠ[O(d/t)] ΣΠ[t] formulas, which are depth 4 formulas with the stated bounds on the fan-ins of the Π gates. A recent depth reduction result of Tavenas (MFCS, 2013) shows that any n-variate degree d = nO(1) polynomial computable by a circuit of size poly(n) can also be computed by a depth 4 ΣΠ[O(d/t)] ΣΠ[t] formula of top fan-in nO(d/t). We show that any such formula computing IMMn,d has top fan-in nΩ(d/t), proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi (ECCC, 2013) which gives a similar lower bound for an explicit polynomial in VNP.Keywords
Funding Information
- Indo-French Centre for the Promotion of Advanced Research
This publication has 18 references indexed in Scilit:
- Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits2014
- Improved Bounds for Reduction to Depth 4 and Depth 32013
- Arithmetic circuits: The chasm at depth four gets widerTheoretical Computer Science, 2012
- Arithmetic Circuits: A Survey of Recent Results and Open QuestionsFoundations and Trends® in Theoretical Computer Science, 2010
- Lower Bounds and Separations for Constant Depth Multilinear Circuitscomputational complexity, 2009
- Multi-linear formulas for permanent and determinant are of super-polynomial sizeJournal of the ACM, 2009
- Balancing Syntactically Multilinear Arithmetic Circuitscomputational complexity, 2008
- Characterizing Valiant's algebraic complexity classesJournal of Complexity, 2008
- Lower bounds on arithmetic circuits via partial derivativescomputational complexity, 1996
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984