DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.17

Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits

Authors: Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta, Nir Shalmon, and Amir Shpilka

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

A depth-4 algebraic circuit with top fan-in k and bottom fan-in 2 is a circuit Φ of the form Φ = ∑_{i = 1}^k ∏_{j = 1}^{m_i} Q_{ij}, where the polynomials Q_{ij} ∈ 𝕂[x₁, …, x_n] have degree at most 2. The class of all such circuits is denoted by Σ^k Π Σ Π². We say that the circuit Φ is an identity if it formally computes the zero polynomial. An important parameter of Σ^k Π Σ Π² circuits Φ is their (linear) rank, which is defined as the vector space dimension of the polynomials {Q_{ij}}_{i ∈ [k], j ∈ [m_i]}. We prove that, when the base field 𝕂 is of characteristic zero, the rank of any (simple and minimal) Σ^k Π Σ Π² identity is upper bounded by a function which depends only on the top fan-in k. This result makes progress on [Beecken et al., 2013], being the first work to establish a bound on the rank of such identities that depends only on the top fan-in. Moreover, when combined with [Beecken et al., 2013], our main result yields the first deterministic, polynomial time PIT algorithm for Σ^k Π Σ Π² circuits. One of the key components of our proof of the rank bounds is the derivation of an approximate Hansen-type result, which is interesting in its own right. This result can be seen as an algebraic and higher-dimensional analogue of the approximate Sylvester-Gallai result of [Ai et al., 2014], and a distinct approximate fractional Sylvester-Gallai result than the one from [Garg et al., 2023]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen’s theorem by [Boaz Barak et al., 2013]. This paper is an extended abstract of the full version of the paper, which can be found at [Garg et al., 2026].

Cite as

Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta, Nir Shalmon, and Amir Shpilka. Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2026.17,
  author =	{Garg, Abhibhav and Oliveira, Rafael and Sengupta, Akash Kumar and Shalmon, Nir and Shpilka, Amir},
  title =	{{Rank Bounds and Polynomial-Time PIT for \Sigma^k \Pi \Sigma \Pi² Circuits}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.17},
  URN =		{urn:nbn:de:0030-drops-270599},
  doi =		{10.4230/LIPIcs.CCC.2026.17},
  annote =	{Keywords: Sylvester-Gallai Theorems, Polynomial Identity Testing, Strong Algebras}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.152

Partial Derivative Complexity of a Product of Linearly Independent Quadratics

Authors: Nir Shalmon and Amir Shpilka

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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 binom(n,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₁,… ,g_r ∈ ℂ[𝐱], the partial derivative complexity of the product ∏_{i=1}^r g_i(𝐱) grows exponentially with r (see [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(Ω(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, 2020; 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.

Cite as

Nir Shalmon and Amir Shpilka. Partial Derivative Complexity of a Product of Linearly Independent Quadratics. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 152:1-152:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shalmon_et_al:LIPIcs.ICALP.2026.152,
  author =	{Shalmon, Nir and Shpilka, Amir},
  title =	{{Partial Derivative Complexity of a Product of Linearly Independent Quadratics}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{152:1--152:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.152},
  URN =		{urn:nbn:de:0030-drops-265411},
  doi =		{10.4230/LIPIcs.ICALP.2026.152},
  annote =	{Keywords: algebraic complexity theory, partial derivatives, arithmetic circuits, quadratic polynomials}
}

Search Results

Documents authored by Shalmon, Nir

Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits

Abstract

Cite as

Partial Derivative Complexity of a Product of Linearly Independent Quadratics

Abstract

Cite as

Thanks for your feedback!

Could not send message