An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
Authors:
- Neeraj KayalNKNeeraj Kayal
- Nutan LimayeNLNutan Limaye
- Chandan SahaCSChandan Saha
- Srikanth SrinivasanSSSrikanth Srinivasan
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 61-70
Abstract
We show here a 2 Ω(√d·log N) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d 3 in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Σ i Π j Q ij , where the Qij's are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Σi,j (Number of monomials of Q ij ) ≥ 2 Ω(√d·log N) . The above mentioned family, which we refer to as the NisanWigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results [1], [2], [3], [4], [5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of [6] and the N Ω(log log N) lower bound in the independent work of [7].Keywords
This publication has 20 references indexed in Scilit:
- Arithmetic circuits: The chasm at depth four gets widerTheoretical Computer Science, 2012
- Partial Derivatives in Arithmetic Complexity and BeyondFoundations and Trends® in Theoretical Computer Science, 2011
- 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
- Perturbed Identity Matrices Have High Rank: Proof and ApplicationsCombinatorics, Probability and Computing, 2009
- Stirling's Approximation for n!: The Ultimate Short Proof?The American Mathematical Monthly, 2000
- Lower bounds on arithmetic circuits via partial derivativescomputational complexity, 1996
- A complexity theory based on Boolean algebraJournal of the ACM, 1985
- Fast Parallel Computation of Polynomials Using Few ProcessorsSIAM Journal on Computing, 1983