Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-065 | 2nd May 2026 08:22

Partial Derivative Complexity of a Product of Linearly Independent Quadratics

RSS-Feed




TR26-065
Authors: Nir Shalmon, Amir Shpilka
Publication: 2nd May 2026 08:22
Downloads: 28
Keywords: 


Abstract:

The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding the measure of explicit polynomials from below, and in some cases, a sharp estimate is required. For example, a frequently used fact is that the dimension of the space spanned by order $k$ partial derivatives of a product of $n$ linearly independent linear functions is ${n\choose k}$.

Beyond the linear case, however, not much is known about the behavior of the (general) partial derivative measure under multiplication. In particular, it has been conjectured that for algebraically independent polynomials $g_1,\dots,g_r \in \mathbb{C}[\mathbf{x}]$, the partial derivative complexity of the product $\prod_{i=1}^{r}{g_i(\mathbf{x})}$ grows exponentially with $r$ (see Question 42 in (Chaugule et al., 2023)), but prior to this work such bounds were only known when the $g_i$'s are linear polynomials, or satisfy additional restrictions.

In this paper, we show a lower bound of $\exp(\Omega(r^{1/6}))$ for the measure of a product of $r$ linearly independent quadratic polynomials. This is the first result to show such a lower bound on the partial derivative measure of a product of nonlinear polynomials, without any further restrictions. Interestingly, we only assume linear independence, which is weaker than algebraic independence. Our proof relies on algebraic-geometric and combinatorial techniques, combining the Jacobian approach of (Chaugule et al., 2023) together with the theory of wide algebras introduced in (Ananyan and Hochster, 2018; Oliveira and Sengupta, 2022; Garg et al., 2023). To our knowledge, this is the first use of wide-algebra techniques for proving lower bounds on partial derivative complexity, and one of the first applications of these techniques outside the context of Sylvester-Gallai type problems.



ISSN 1433-8092 | Imprint