ECCC-Report TR15-109https://eccc.weizmann.ac.il/report/2015/109Comments and Revisions published for TR15-109en-usWed, 01 Jul 2015 11:19:58 +0300
Paper TR15-109
| An exponential lower bound for homogeneous depth-5 circuits over finite fields |
Mrinal Kumar,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2015/109In 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 : d \in N\}$ of polynomials in $VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, such that over all finite fields $F_q$, any homogeneous depth-$5$ circuit which computes $P_d$ must have size at least $\exp(\Omega_q(\sqrt{d}))$.
To the best of our knowledge, this is the first super-polynomial lower bound for this class for any field $F_q \neq F_2$.
Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-$4$ circuits [GKKS14, FLMS14, KLSS14, KS14b] and for non-homogeneous depth-$3$ circuits over finite fields [GK98, GR00].
Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from $F_q^n \rightarrow F_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 [KS14b].
Wed, 01 Jul 2015 11:19:58 +0300https://eccc.weizmann.ac.il/report/2015/109