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-084 | 20th May 2026 04:26

Rank bounds and polynomial-time PIT for $\Sigma^k \Pi \Sigma \Pi^2$ circuits

RSS-Feed

Abstract:

A depth-4 algebraic circuit with top fan-in $k$ and bottom fan-in $2$ is a circuit $\Phi$ of the form $\Phi = \sum_{i=1}^k \prod_{j=1}^{m_i} Q_{ij}$, where the polynomials $Q_{ij} \in \mathbb{K}[x_1, \ldots, x_n]$ have degree at most $2$.
The class of all such circuits is denoted by $\Sigma^k \Pi \Sigma \Pi^2$.
We say that the circuit $\Phi$ is an identity if it formally computes the zero polynomial.
An important parameter of $\Sigma^k \Pi \Sigma \Pi^2$ circuits $\Phi$ is their (linear) rank, which is defined as the vector space dimension of the polynomials $\{Q_{ij}\}_{i \in [k], j \in [m_i]}$.

We prove that, when the base field $\mathbb{K}$ is of characteristic zero, the rank of any (simple and minimal) $\Sigma^k \Pi \Sigma \Pi^2$ identity is upper bounded by a function which depends only on the top fan-in $k$.
This result makes progress on [BMS13, Conjecture 28], 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 [BMS13, Theorem 2], our main result yields the first deterministic, \emph{polynomial time} PIT algorithm for $\Sigma^k \Pi \Sigma \Pi^2$ 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 [ADSW14], and a distinct approximate fractional Sylvester-Gallai result than the one from [GOPS23]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen's theorem by [BDWY13].



ISSN 1433-8092 | Imprint