Name
Abstract | ||
|---|---|---|
In this paper, we show exponential lower bounds for the class of homogeneous depth-5 circuits over all small finite fields. More formally, we show that there is an explicit family {P-d} of polynomials in VNP, where P-d is of degree d in n = d(O(1)) variables, such that over all finite fields GF(q), any homogeneous depth-5 circuit which computes Pd must have size at least exp(Omega(q)(root d)). To the best of our knowledge, this is the first super-polynomial lower bound for this class for any non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)(n) to GF(q) as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [Kumar-Saraf]. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4230/LIPIcs.CCC.2017.31 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
arithmetic circuits,lower bounds,separations,depth reduction | Journal | 79 |
ISSN | Citations | PageRank |
1868-8969 | 6 | 0.42 |
References | Authors | |
15 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mrinal Kumar 0001 | 1 | 64 | 9.94 |
| Ramprasad Saptharishi | 2 | 184 | 13.72 |