Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917998510473216 |
|---|---|
| author | Garg, Abhibhav Oliveira, Rafael Sengupta, Akash Kumar |
| author_facet | Garg, Abhibhav Oliveira, Rafael Sengupta, Akash Kumar |
| contents | 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 $Σ^{3}ΠΣΠ^{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 $Σ^{3}ΠΣΠ^{d}$ circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14729 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem Garg, Abhibhav Oliveira, Rafael Sengupta, Akash Kumar Computational Complexity 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 $Σ^{3}ΠΣΠ^{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 $Σ^{3}ΠΣΠ^{d}$ circuits. |
| title | Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2504.14729 |