Depth 4 Lower Bounds, Determinantal Complexity : A Unified Approach
Publisher Information
Abstract
Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth 4 \Sigma\Pi\Sigma\Pi circuit of size 2^{O(\sqrt{n}\log n)} (see Tavenas (2013)). So, to prove VP\neq VNP it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{\omega(\sqrt{n}\log n)} size depth 4 circuits. Soon after Tavenas’ result, for two different explicit polynomials, depth 4 circuit size lower bounds of 2^{\Omega(\sqrt{n}\log n)} have been proved (see Kayal-Saha-Saptharishi (2013) and Fournier-Limaye-Malod-Srinivasan (2013)). In particular, using combinatorial design Kayal et al. construct an explicit polynomial in VNP that requires depth 4 circuits of size 2^{\Omega(\sqrt{n}\log n)} and Fournier et al. show that the iterated matrix multiplication polynomial (which is in VP) also requires 2^{\Omega(\sqrt{n}\log n)} size depth 4 circuits.
In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies this property would achieve a similar depth 4 circuit size lower bound. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a simple unified lower bound analysis for the above mentioned polynomials.
Another goal of this paper is to compare our current knowledge of the depth 4 circuit size lower bounds and the determinantal complexity lower bounds. Currently the best known determinantal complexity lower bound is \Omega(n^2) for Permanent of a n\times n matrix (which is a n^2-variate and degree n polynomial) (due to Cai, Chen and Li (2008)). We prove that the determinantal complexity of the iterated matrix multiplication polynomial is \Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth 4 circuit size and determinantal complexity. Our result also settles the determinantal complexity of the iterated matrix multiplication polynomial to \Theta(dn).
To the best of our knowledge, a \Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for any constant d>1 (cf. Jansen (2011)).