ECCC-Report TR14-005https://eccc.weizmann.ac.il/report/2014/005Comments and Revisions published for TR14-005en-usTue, 14 Jan 2014 06:57:08 +0200
Paper TR14-005
| An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas |
Neeraj Kayal,
Nutan Limaye,
Chandan Saha,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2014/005We 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).Tue, 14 Jan 2014 06:57:08 +0200https://eccc.weizmann.ac.il/report/2014/005