Paper Info
Title
On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields.
Abstract
In a surprising recent result, Gupta–Kamath–Kayal–Saptharishi have proved that over Q any nO(1)-variate and n-degree polynomial in VP can also be computed by a depth three ΣΠΣ circuit of size 2O(nlog3/2⁡n).2 Over fixed-size finite fields, Grigoriev and Karpinski proved that any ΣΠΣ circuit that computes the determinant (or the permanent) polynomial of a n×n matrix must be of size 2Ω(n). In this paper, for an explicit polynomial in VP (over fixed-size finite fields), we prove that any ΣΠΣ circuit computing it must be of size 2Ω(nlog⁡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 nO(1)-variate and n-degree polynomials in VP by depth 3 circuits of size 2o(nlog⁡n). The result of Grigoriev and Karpinski can only rule out such a possibility for ΣΠΣ circuits of size 2o(n).
Year
DOI
Venue
2014
10.1016/j.ic.2017.04.007
Information and Computation
DocType
Volume
ISSN
Journal
256
0890-5401
Citations 
PageRank 
References 
0
0.34
16
Authors
2
Name
Order
Citations
PageRank
Suryajith Chillara1143.68
Partha Mukhopadhyay29112.71