Rank Bounds and PIT for Σ³ ΠΣΠ^d circuits via a non-linear Edelstein-Kelly theorem

2025/04/20 by Abhibhav Garg, Rafael S. Oliveira, Garg, Abhibhav +3
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2504.14729

openalex publication_date 2025/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

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 Σ³ΠΣΠ^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 Σ³ΠΣΠ^d circuits.

Related

• Polynomial time deterministic identity testingalgorithm for Σ^[3]ΠΣΠ^[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials
• Deterministic Depth-4 PIT and Normalization
• PIT for depth-4 circuits and Sylvester-Gallai conjecture for polynomials
• An Almost Optimal Rank Bound for Depth-3 Identities
• On top fan-in vs formal degree for depth-3 arithmetic circuits