Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
verfasst von : Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \({\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, and may be of independent interest.