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.