An exponential lower bound for homogeneous depth-5 circuits over finite fields
An exponential lower bound for homogeneous depth-5 circuits over finite fields
复制标题
有限域上齐次深度 5 电路的指数下界
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ramprasad Saptharishi
中科院分区：
文献类型：
--
作者：
Mrinal Kumar;Ramprasad Saptharishi
在这篇文章中，我们给出了一类齐次深度-$5$回路在所有小有限域上的指数下界。更正式地，我们证明了在$mathsf{VNP}$中存在一个显式多项式族${P_d：D in mathbb{N}}$，其中$P_d$是$n=d^{O(1)}$变量中$d$的次数，使得在所有有限域$mathbb{F}_q$中，任何计算$P_d$的齐次深度-$5$回路必至少有$exp(Omega_q(Sqrt{d}))$.
就我们所知，这是任何域$mathbb{F}_q的此类的第一个超多项式下界
EQ mathbb{F}_2$。
我们的证明建立在证明有限域上的齐次深度-$4$回路[GKKS13，FLMS13，KLSS14，KS14]和非齐次深度-$3$回路[GK98，GR00]下界的方法上。我们的主要见解是将多项式的移位偏导数空间视为来自$mathbb{F}_q^n的函数空间
而不是将它们视为形式多项式的空间，而是建立在对Kumar和Saraf下界的更紧密分析的基础上[KS14]。
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
eq 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
ightarrow 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].