Name
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 < log N/log log 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 EllEll 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 EITE model (i.e. EllEll formulas with bottom fan -in 1). Our main technical lemma gives a lower bound for the ranks of certain inclusion-like matrices, and may be of independent interest. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-662-48054-0_27 | Lecture Notes in Computer Science |
DocType | Volume | Issue |
Journal | 9235 | 1 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.38 |
References | Authors | |
16 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hervé Fournier | 1 | 185 | 18.10 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Meena Mahajan | 3 | 688 | 56.90 |
| Srikanth Srinivasan | 4 | 132 | 21.31 |