Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-051 | 21st April 2025 17:11

Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem

RSS-Feed

Abstract:

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 fanin (denoted $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial.
This settles a stronger form of Conjecture 1 in Gupta (2014) when $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 $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.



ISSN 1433-8092 | Imprint