Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials
Shir Peleg, Amir Shpilka
2021Year
9Citations
6Top-tier citations
Abstract
In this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS13] and Gupta [Gup14], by proving an analog of a theorem of Edelstein and Kelly for quadratic polynomials. As immediate corollary we obtain the first deterministic polynomial time black-box algorithm for testing zeroness of Σ [3] ΠΣΠ [2] circuits.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 628ccc11-29be-4778-bd2f-cfe4c794ffd5Cited by top-tier papers6
- Superpolynomial Lower Bounds Against Low-Depth Algebraic CircuitsNutan Limaye, Srikanth Srinivasan, Sébastien TavenasFOCS 2021 · 26 citations
- Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsRobert Andrews, Michael A. ForbesSTOC 2022 · 6 citations
- Demystifying the border of depth-3 algebraic circuitsPranjal Dutta, Prateek Dwivedi, Nitin SaxenaFOCS 2021 · 6 citations
- Radical Sylvester-Gallai Theorem for CubicsRafael Oliveira, Akash Kumar SenguptaFOCS 2022 · 3 citations
- Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-InShubhangi Saraf, Devansh Shringi, Narmada VaradarajanSTOC 2026 · 2 citations
Related papers
- Rank Bounds and PIT for depth-4 circuits with top fan-in 3 and constant bottom fan-in via a non-linear Edelstein-Kelly theoremAbhibhav Garg, Rafael Oliveira, Akash Kumar SenguptaFOCS 2025 · 2 citations
- Reconstruction of Depth-4 Multilinear CircuitsVishwas Bhargava, Shubhangi Saraf, Ilya VolkovichSODA 2020 · 5 citations
- Strong Algebras and Radical Sylvester-Gallai ConfigurationsRafael Oliveira, Akash Kumar SenguptaSTOC 2024 · 1 citation
- Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum CircuitsNolan J. Coble, Matthew CoudronFOCS 2021 · 3 citations
- Fast Deterministic Chromatic Number under the Asymptotic Rank ConjectureAndreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski et al.SODA 2025 · 1 citation
