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

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.

43 pages. Added reference to concurrent work