An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

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