Back to Arithmetic Circuits
Back to notes

Lower bounds - Depth 3

20%

Partial derivatives

Let $\mathbb{F}$ be a field and $f\in\mathbb{F}[x_1,x_2,\dots,x_n]$, for any $k\in\N$, define the $k$th order partial derivative of $f$ as follows. $$\partial_{=k}f = {\frac{\partial^k f}{\prod_{i\in S}\partial x_i}:\ S\subseteq[n],\ \card{S}=k }.$$ Define the dimension of $\partial_{=k}f$ as $dim(\partial_{=k}f)$ to be the dimension of the linear span of $\partial_{=k}f$.

It turns out that the dimension of the partial derivative has the following nice properties to be a good complexity measure. Let $\Gamma_k(f)=dim(\partial_{=k}f)$.

Let $\mathbb{F}$ be a field, $f,g\in\mathbb{F}[x_1,x_2,\dots,x_n]$, and $\alpha\in\mathbb{F}$, $\alpha\neq0$. For any $k\in\N$, we have
• $\Gamma_k(\alpha\cdot f)=\Gamma_k(f)$.
• (*subadditive property*) $\Gamma_k(f+g)\leq\Gamma_k(f)+\Gamma_k(g)$.

• $\Gamma_k(\alpha\cdot f)=\Gamma_k(f)$. For any $h_1,h_2,\dots,h_s\in\partial_{=k}f$ and $a_1,a_2,\dots,a_s\in\mathbb{F}$, $\sum_{i\in[s]}a_i\cdot h_i=\sum_{i\in[s]}(a_i\cdot\alpha^{-1})\alpha h_i$ such that $a_i$ is non-zero iff $a_i\cdot\alpha^{-1}$ is non-zero. As $\alpha h_i\in\partial_{=k}(\alpha\cdot f)$, we have $\Gamma_k(\alpha\cdot f)=\Gamma_k(f)$.
• $\Gamma_k(f+g)\leq\Gamma_k(f)+\Gamma_k(g)$. Let $\Gamma_k(f)=d_f$ and $\Gamma_k(g)=d_g$. By the definition of linearly independence, there exists non-zero $a_1,a_2,\dots,a_{d_f},b_1,b_2,\dots,b_{d_g}\in\mathbb{F}$, $f_1,f_2,\dots,f_{d_f}\in\partial_{=k}f$, and $g_1,g_2,\dots,g_{d_g}\in\partial_{=k}g$ such that $\sum_{i\in[d_f]}a_if_i=\sum_{i\in[d_g]b_ig_i}=0$. That is, $\sum_{i\in[d_f]}a_if_i+\sum_{i\in[d_g]b_ig_i}=0$ and thus $dim(f+g)\leq d_f+d_g$.

Lower bounds for h-$\Sigma\Pi\Sigma$

Nisan and Wigderson proved the following exponential lower bounds for h-$\Sigma\Pi\Sigma$ using partial derivatives. The idea is based on the observation that small $\Sigma\Pi\Sigma$ circuit has small partial derivatives compleixty while that of elementary symmetric polynomials is large.

Let $f$ be a polynomial computed by a $\Sigma\Pi^{[d]}\Sigma$ circuit of size $s$, then $$\Gamma_k(f)\leq s\cdot \binom{d}{k}.$$

First, consider $\Pi^{[d]}\Sigma$ which computes polynomial of the form $g=g_1g_2\cdots g_d$ where $g_i$ is linear function. As a result, $\partial_{=k}g\subseteq\{\prod_{i\in S}g_i:\ S\subseteq[d],\ \card{S}=d-k \}$ and thus $\Gamma_k(g)\leq\binom{d}{k}$. Next, by the subadditive property of $\Gamma_k$, we have the desired upper bound.

The following lemma shows that the partial derivative complexity of elementary symmetric polynomials is large.

Let $n,d,k\in\N$ such that $k\leq d\leq n$. We have $$\Gamma_k(\Sym_{n,d})=\min\{\binom{n}{k},\binom{n}{d-k}\}.$$ Specifically, pick $d=2k$, we have $$\Gamma_k(\Sym_{n,d}) = \binom{n}{d/2}\geq(\frac{2n}{d})^{d/2}.$$

• (Upper bound) Observe that $dim(\partial_{=k}Sym_{n,d})\leq\card{\partial_{=k}Sym_{n,d}}\leq\binom{n}{k}$ since there are only $\binom{n}{k}$ distinct choice of monomials of degree $k$. Also, as the polynomials in $\partial_{=k}Sym_{n,d}$ are all sum of monomials of degree $d-k$, we have $dim(\partial_{=k}Sym_{n,d})\leq\binom{n}{d-k}$.
• (Lower bound)

Combine the two lemmas, we have the following theorem.

For any $n,d\in\N$, any h-$\Sigma\Pi\Sigma$ circuir for $\Sym_{n,d}$ has size at least $n^{\Omega(d)}$.

By the above two lemmas, we know that any h-$\Sigma\Pi\Sigma$ circuit for $\Sym_{n,d}$ needs to have size s\geq\frac{(\frac{2n}{d})^{d/2}}{\binom{d}{d/2}}\geq n^{\Omega(d)}. \end{eqution}

Note that the lower bound here is for homogeneous $\Sigma\Pi\Sigma$ circuit. It turns out that non-homogeneous provides exponential saving for elementary symmetric polynomials.