Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-005 | 14th January 2014 06:47

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas



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

ISSN 1433-8092 | Imprint