On the complexity of partial derivatives

Abstract : The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is ♯P-hard and we ask whether it belongs to ♯P. We analyze the " trace method " , recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees. A slightly shorter version of this paper was presented at STACS'17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitov's work on tensor rank.
Keywords :
Type de document :
Pré-publication, Document de travail
2016
Domaine :

Littérature citée [21 références]

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01345746
Contributeur : Pascal Koiran <>
Soumis le : mardi 30 mai 2017 - 14:35:55
Dernière modification le : mardi 24 avril 2018 - 13:52:54

Fichiers

partials2.arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : ensl-01345746, version 2
• ARXIV : 1607.05494

Citation

Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé. On the complexity of partial derivatives. 2016. 〈ensl-01345746v2〉

Métriques

Consultations de la notice

173

Téléchargements de fichiers