AN EXPONENTIAL LOWER BOUND FOR HOMOGENEOUS DEPTH FOUR ARITHMETIC FORMULAS

We show here a 2(Omega(root d center dot logN)) size lower bound for homogeneous depth four arithmetic formulas over fields of characteristic zero. 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 = Sigma(i)Pi(j)Q(ij), where the Q(ij)'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 Sigma(i,j) (number of monomials of Q(ij)) >= 2(Omega(root d center dot logN)). The abovementioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on recent lower bound results and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of [N. Kayal et al., in Symposium on Theory of Computing, ACM, New York, 2014, pp. 119-127] and the N-Omega(log logN) lower bound in the independent work of [M. Kumar and S. Saraf, in Automata, Languages, and Programming, Part I, Springer, Berlin, 2014, pp. 751-762]