In a surprising recent result, Gupta et al. [GKKS13b] have proved that over Q any n~O-variate and n-degree polynomial in VP can also be computed by a depth three ΣΠΣ circuit of size 2~(O(n~(1/2) log~(3/2) n))~1. Over fixed-size finite fields, Grigoriev and Karpinski proved that any EΠE circuit that computes the determinant (or the permanent) polynomial of a n × n matrix must be of size 2~(Ω(n)). In this paper, for am explicit polynomial in VP (over fixed-size finite fields), we prove that any ΣΠΣ circuit computing it must be of size 2~(Ω(n log n)). The explicit polynomial that we consider is the iterated matrix multiplication polynomial of n generic matrices of size n×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-variate and n-degree polynomials in VP by depth 3 circuits of size 2°~(n log n). The result of [GK98] can only rule out such a possibility for ΣΠΣ circuits of size 2°~(n). We also give an example of an explicit polynomial (NW_(n,∈)(X)) in VNP (which is 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 of Nisan and Wigderson [NW94], and is closely related to the polynomials considered in many recent papers where strong depth 4 circuit size lower bounds were shown [KSS13,KLSS14,KS13b,KS14].
展开▼
