Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-118 | 23rd July 2015 12:34

The shifted partial derivative complexity of Elementary Symmetric Polynomials

RSS-Feed




TR15-118
Authors: Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
Publication: 23rd July 2015 12:57
Downloads: 909
Keywords: 


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 < \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 $\Sigma\Pi\Sigma\Pi$ 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 homogeneous $\Sigma\Pi\Sigma$ model (i.e. $\Sigma\Pi\Sigma\Pi$ formulas with bottom fan-in $1$).

Our main technical lemma gives a lower bound for the ranks of certain inclusion-like matrices.



ISSN 1433-8092 | Imprint