Revised: September 1, 2016

Published: September 25, 2017

**Keywords:**arithmetic circuits, depth-4 circuits, inclusion matrices

**Categories:**complexity theory, circuit complexity, arithmetic circuits, depth-4 circuits, inclusion matrices

**ACM Classification:**F.1.3, F.2.2

**AMS Classification:**68Q17, 68Q15, 68Q25

**Abstract:**
[Plain Text Version]

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 $\spsp$ 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 $\sps$ model (i.e., $\spsp$ 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.