2026-07-23T17:39:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27059 2026-07-23T11:36:19Z ddc:004 open_access

Rank Bounds and Polynomial-Time PIT for Σ^k Π Σ Π² Circuits Garg, Abhibhav Oliveira, Rafael Sengupta, Akash Kumar Shalmon, Nir Shpilka, Amir Sylvester-Gallai Theorems Polynomial Identity Testing Strong Algebras 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhibhav Garg and Rafael Oliveira and Akash Kumar Sengupta and Nir Shalmon and Amir Shpilka 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.17 urn:nbn:de:0030-drops-270599 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode