Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-109 | 1st July 2015 11:09

An exponential lower bound for homogeneous depth-5 circuits over finite fields


Authors: Mrinal Kumar, Ramprasad Saptharishi
Publication: 1st July 2015 11:19
Downloads: 649


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 : 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].

ISSN 1433-8092 | Imprint