pdf icon
Volume 13 (2017) Article 9 pp. 1-34
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Received: September 29, 2015
Revised: September 1, 2016
Published: September 25, 2017
Download article from ToC site:
[PDF (350K)]    [PS (2145K)]    [PS.GZ (433K)]
[Source ZIP]
Keywords: arithmetic circuits, depth-4 circuits, inclusion matrices
ACM Classification: F.1.3, F.2.2
AMS Classification: 68Q17, 68Q15, 68Q25

Abstract: [Plain Text Version]

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