An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Authors:
  • NKNeeraj Kayal
    Neeraj Kayal
  • NLNutan Limaye
    Nutan Limaye
  • CSChandan Saha
    Chandan Saha
  • SSSrikanth Srinivasan
    Srikanth Srinivasan

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].

This publication has 20 references indexed in Scilit: