TR14-005 Authors: Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

Publication: 14th January 2014 06:57

Downloads: 3415

Keywords:

We show here a $2^{\Omega(\sqrt{d} \cdot \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 = \sum_{i} \prod_{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 the total number of monomials in all the $Q_{ij}$'s put together must be at least $2^{\Omega(\sqrt{d} \cdot \log N)}$.

The abovementioned family which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. For polynomial families in VP we show the following: Any homogeneous depth four arithmetic formula computing the Iterated Matrix Multiplication polynomial $IMM_{n,d}$ --- the $(1,1)$-th entry of the product of $d$ generic $n \times n$ matrices --- has size $n^{\Omega(\log n)}$, if $d = \Omega(\log^2 n)$. Moreover, any homogeneous depth four formula computing the determinant polynomial $Det_n$ --- the determinant of a generic $n \times n$ matrix --- has size $n^{\Omega(\log n)}$. Our work builds on the recent lower bound results and yields an improved quantitative bound as compared to the recent indepedent work by Kumar and Saraf (ECCC TR13-181).