Paper detail

On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields

Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variate and $n$-degree polynomial in VP can also be computed by a depth three $ΣΠΣ$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-size finite fields, Grigoriev and Karpinski proved that any $ΣΠΣ$ circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{Ω(n)}$ [GK1998]. In this paper, we prove that over fixed-size finite fields, any $ΣΠΣ$ circuit for computing the iterated matrix multiplication polynomial of $n$ generic matrices of size $n\times n$, must be of size $2^{Ω(n\log n)}$. The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits of size $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibility for depth 3 circuits of size $2^{o(n)}$. We also give an example of an explicit polynomial ($NW_{n,ε}(X)$) in VNP (not known to be in VP), for which any $ΣΠΣ$ circuit computing it (over fixed-size fields) must be of size $2^{Ω(n\log n)}$. The polynomial we consider is constructed from the combinatorial design. An interesting feature of this result is that we get the first examples of two polynomials (one in VP and one in VNP) such that they have provably stronger circuit size lower bounds than Permanent in a reasonably strong model of computation. Next, we prove that any depth 4 $ΣΠ^{[O(\sqrt{n})]}ΣΠ^{[\sqrt{n}]}$ circuit computing $NW_{n,ε}(X)$ (over any field) must be of size $2^{Ω(\sqrt{n}\log n)}$. To the best of our knowledge, the polynomial $NW_{n,ε}(X)$ is the first example of an explicit polynomial in VNP such that it requires $2^{Ω(\sqrt{n}\log n)}$ size depth four circuits, but no known matching upper bound.