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

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:d\in \mathbb{N}\}$ of polynomials in $\mathsf{VNP}$, where $P_d$ is of degree $d$ in $n=d^{O(1)}$ variables, such that over all finite fields ${\mathbb{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 ${\mathbb{F}}_q\ne {\mathbb{F}}_2$. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-$4$ circuits [GKKS13, FLMS13, KLSS14, KS14] 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 ${\mathbb{F}}_q^n\to {\mathbb{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 [KS14].

Cited by in corpus (2)

• Barriers for Rank Methods in Arithmetic Complexity
• Towards an algebraic natural proofs barrier via polynomial identity testing