Source-linked AI summary
On the complexity of partial derivatives
Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé
TL;DR
The paper studies the computational complexity of the dimension of a polynomial’s space of partial derivatives when the polynomial is given sparsely. It proves #P-hardness, develops a polynomial-time trace-method lower bound, and leaves approximation with reasonable guarantees open.
Problem
The paper asks how hard it is to compute the dimension of the span of partial derivatives for a polynomial given as a sum of its nonzero monomials.
Method
The paper analyzes the trace method and uses the proxy Tr(B)^2/Tr(B^2) to obtain a polynomial-time computable lower bound on partial-derivative dimension.
Results
Computing partial-derivative dimension is #P-hard, even for multilinear homogeneous polynomials with coefficients in {0, 1}.
Takeaways & Limitations
The trace method yields efficiently computable lower bounds and closed-form bounds for the dimension of spaces of partial derivatives.
Takeaways & Limitations
The existence of an approximation algorithm with a reasonable performance guarantee remains open, and the trace proxy performs poorly on symmetric polynomials.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies the complexity of computing partial-derivative dimensions from sparse polynomials. It proves #P-hardness, develops polynomial-time lower bounds via the trace method, and identifies approximation and membership questions that remain open.
- Computing dim ∂*f from an expanded polynomial is #P-hard, even for multilinear homogeneous polynomials with coefficients in {0, 1}.
- The hardness proof uses a #P-complete problem for counting faces of simplicial complexes, reduced from counting independent sets in graphs.
- The paper derives closed-form lower bounds from the trace method and compares them with a bound based on a single extremal monomial.
- The trace method replaces a derivative-matrix rank by the proxy rank Tr(B)^2/Tr(B^2), which is computable in polynomial time despite B potentially having exponential size.
- The trace method can perform poorly on elementary symmetric polynomials, proving only rank larger than 1 when the derivative matrix has full rank.
- Open problems include whether the exact dimension problems belong to #P and whether efficient approximation algorithms with reasonable guarantees exist.
2 Elementary bounds
The elementary bounds analyze partial derivatives through monomial bases and matrix structure. They provide computable bounds by selecting an extremal monomial and establish basic upper bounds through derivative linearity.
- Scaled monomials make differentiation simple: ∂βxα = xα−β, with xα−β defined as zero when an exponent becomes negative.
- For a monomial, dim ∂=kxα can be computed for all k using O((deg f)^2) additions.
- Derivative linearity gives upper bounds such as dim ∂=k(f + g) ≤ dim ∂=kf + dim ∂=kg, while adding monomials need not increase the dimension.
- Theorem 1 guarantees a monomial m in f whose derivative-space dimension lower-bounds that of f for every derivative order k.
- The extremal monomial may be chosen using a compatible monomial order, and changing the order allows any Newton-polytope vertex to serve this role.
- The proof establishes linear independence by placing the relevant derivative matrix in row-echelon form with no zero rows.
3 The trace method
The trace method converts the partial-derivative dimension problem into a proxy-rank computation, yielding polynomial-time lower bounds and closed-form estimates. Its guarantees can be strong for some polynomials but fail badly on elementary symmetric polynomials.
- Trace method: The global trace-method analysis lower-bounds the partial-derivative space using a matrix built from derivatives taken at most once per variable.The matrix M has rows indexed by k-subsets, and B=M^T·M is used to lower-bound rank(M).
- 0/1 coefficients: Theorem 5 uses all monomials to improve on the single-extremal-monomial bound when most monomials have large support.Its advantage is especially visible when a few small-support monomials would weaken the extremal-monomial estimate.
- Extension to real coefficients: For real polynomials, Theorem 8 extends the lower bound beyond 0/1 coefficients, while equal coefficient magnitudes recover the 0/1-style bound.The extension uses the same matrix construction and a symmetric-matrix trace inequality.
- Polynomial-time computable lower bounds: The proxy rank Tr(B)^2/Tr(B^2) is computable in polynomial time and provides a lower bound on dim ∂=kf despite B’s potentially exponential size.The paper also derives a closed-form lower bound below the proxy rank.
- Elementary symmetric polynomials: For fixed d and k, elementary symmetric polynomials make the proxy rank converge to 1 while the true partial-derivative dimension grows without bound.The associated partial-derivative matrix is full rank, demonstrating arbitrarily large gaps between proxy rank and dimension.
- Elementary symmetric polynomials: The gap can also become arbitrarily large when k and d grow proportionally with n under the stated parameter conditions.For 0 < 2α < β < 1/2, the exponent governing the gap is negative.
4 ♯P-hardness result for the space of partial derivatives
The paper proves that computing the dimension of the space of partial derivatives is #P-hard, even for multilinear homogeneous polynomials with Boolean coefficients. The reduction passes through counting faces of pure simplicial complexes and constructs a polynomial whose derivative-space dimension encodes that count.
- Hardness theorem: The hardness result holds for multilinear homogeneous polynomials with coefficients in {0, 1}, including a degree and variable-count refinement.The refined statement concerns degree n − 1 and polynomials with m monomials in n + m variables.
- Counting faces: #P-complete counting of generated faces reduces to the derivative-dimension problem.The reduction starts from the number of faces in a simplicial complex generated by a family of subsets.
- Counting faces: #P-hardness remains true when the simplicial complex is pure, with all generating sets having equal cardinality.Purity ensures the associated polynomial is homogeneous.
- Polynomial construction: Given generating sets F_i, the construction uses monomials m_i = product over j in F_i of X_j and f = sum_i Y_i m_i.The resulting polynomial is multilinear and homogeneous of degree d + 1 in m + n variables.
- Derivative-space basis: A basis for the derivative space consists of 2|∆| polynomials formed from derivatives involving either one Y_i or no Y_i.The proof establishes spanning, linear independence, and a direct-sum decomposition of the two families.
- Graph reduction: For a graph G, the construction gives dim ∂+f = 2(2^n − Ind(G) − 1), linking derivative dimension to independent-set counting.The simplicial complex is generated by complements of graph edges, and its faces correspond to complements of dependent sets.