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].

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let 𝕂 be an algebraically closed field of characteristic zero, and let ℱ = {F_1, …, F_m} ⊂ 𝕂[x_1, …, x_N] denote a collection of irreducible homogeneous polynomials of degree at most d, where each F_i is not a scalar multiple of any other F_j for i ≠ j. We define ℱ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials F_i, F_j ∈ ℱ, the following condition is satisfied: ∏_{k≠i, j} F_k ∈ rad (F_i, F_j) . We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function λ : ℕ → ℕ, independent of 𝕂, N, and m, such that any product Sylvester-Gallai configuration must satisfy: dim(span_𝕂(ℱ)) ≤ λ(d). This result generalizes the main theorems from (Shpilka 2019, Peleg and Shpilka 2020, Oliveira and Sengupta 2023), and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree. As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fan-in which compute the zero polynomial. This settles a stronger form of Conjecture 1 in Gupta (2014) when $\mathrm{k}=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information & Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information & Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for these circuits.

A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, where the seminal work of (Kaltofen 1995) yields a randomized, polynomial time algorithm for this problem. However, when $m > 1$, the complexity of the primality testing problem seems much harder. The current best algorithms for this problem are only known to be in EXPSPACE. In this work, we significantly reduce the complexity-theoretic gap for the ideal primality testing problem for the important families of ideals $I$ (namely, radical ideals and equidimensional Cohen-Macaulay ideals). For these classes of ideals, assuming the Generalized Riemann Hypothesis, we show that primality testing lies in $\Sigma_3^p \cap \Pi_3^p$. This significantly improves the upper bound for these classes, approaching their lower bound, as the primality testing problem is coNP-hard for these classes of ideals. Another consequence of our results is that for equidimensional Cohen-Macaulay ideals, we get the first PSPACE algorithm for primality testing, exponentially improving the space and time complexity of prior known algorithms.

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials. More precisely, given a parameter 0 < δ ≤ 1 and a finite collection ℱ of irreducible and pairwise independent polynomials of degree at most 2, we say that ℱ is a (δ, 2)-radical Sylvester-Gallai configuration if for any polynomial F_i ∈ ℱ, there exist δ(|ℱ|-1) polynomials F_j such that |rad (F_i, F_j) ∩ ℱ| ≥ 3, that is, the radical of F_i, F_j contains a third polynomial in the set. We prove that any (δ, 2)-radical Sylvester-Gallai configuration ℱ must be of low dimension: that is dim span_ℂ{ℱ} = poly(1/δ).

Radical membership testing, resp. its special case of Hilbert's Nullstellensatz (HN), is a fundamental computational algebra problem. It is NP-hard; and has a famous PSPACE algorithm due to effective Nullstellensatz bounds. We identify a useful case of these problems where practical algorithms, & improved bounds, could be given---When transcendence degree (tr.deg) r of the input polynomials is smaller than the number of variables n. If d is the degree bound on the input polynomials, then we solve radical membership (even if input polynomials are blackboxes) in around dr time. The prior best was > dn time (always, dn ≥ dr). Also, we significantly improve effective Nullstellensatz degree-bound, when r ≪ n.