The shifted partial derivative complexity of elementary symmetric polynomials

Abstract

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 < lgN=lg lgN. 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 ΣПΣП 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 ΣПΣ model (i. e., ΣПΣП circuits with bottom fan-in 1). Our main technical lemma gives a lower bound for the ranks of certain inclusion-like matrices. © 2017 Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan.