Volume 13 (2017) Article 9 pp. 1-34

The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials

by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan

Received: September 29, 2015
Revised: September 1, 2016
Published: September 25, 2017

$ \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 $\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.

DOI: 10.4086/toc.2017.v013a009

© 2017 Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan
Licensed under a Creative Commons Attribution License (CC-BY)