2026-08-15T13:54:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6996 2024-03-06T10:39:12Z ddc:004 open_access

On the Complexity of Partial Derivatives Garcia-Marco, Ignacio Koiran, Pascal Pecatte, Timothée Thomassé, Stéphan counting complexity simplicial complex lower bounds arithmetic circuits 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ignacio Garcia-Marco and Pascal Koiran and Timothée Pecatte and Stéphan Thomassé 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.37 urn:nbn:de:0030-drops-69964 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.37 eng https://creativecommons.org/licenses/by/3.0/legalcode