Theory of Computing
-------------------
Title : The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Authors : Herve Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan
Volume : 13
Number : 9
Pages : 1-34
URL : https://theoryofcomputing.org/articles/v013a009
Abstract
--------
$ \newcommand{\ie}{i.\,e.} \newcommand{\sps}{\mathrm{\Sigma\Pi\Sigma}}
\newcommand{\spsp}{\mathrm{\Sigma\Pi\Sigma\Pi}} $
We continue the study of the _shifted partial derivative measure_,
introduced by Kayal (ECCC 2012), which has been used to prove many
strong depth-4 circuit lower bounds starting from the work of Kayal,
and that of Gupta et al. (CCC 2013).
We show a strong lower bound on the dimension of the shifted partial
derivative space of the elementary symmetric polynomials of degree $d$
in $N$ variables for $d < \lg N / \lg \lg N$. This extends the work
of Nisan and Wigderson (Computational Complexity 1997), who studied
the _partial derivative space_ of these polynomials. Prior to our
work, there have been no results on the shifted partial derivative
measure of these polynomials.
Our result implies a strong lower bound for elementary symmetric
polynomials in the homogeneous $\Sigma\Pi\Sigma\Pi$ model with bounded
bottom fan-in. This strengthens (under our degree assumptions) a lower
bound of Nisan and Wigderson who proved the analogous result for the
homogeneous $\Sigma\Pi\Sigma\Pi$ model (i.e., $\Sigma\Pi\Sigma\Pi$
circuits with bottom fan-in $1$).
Our main technical lemma gives a lower bound for the ranks of certain
inclusion-like matrices.
An extended abstract of this paper appeared in the
Proceedings of the 40th International Symposium on
Mathematical Foundations of Computer Science, 2015.