Revised: September 1, 2016
Published: September 25, 2017
[PDF (350K)] [PS (2145K)] [Source ZIP]
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.<! -- footnote -- >
An extended abstract of this paper appeared in the Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, 2015.