Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials
Shir Peleg, Amir Shpilka
2021年份
9被引次数
6顶会引用
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper6
- Superpolynomial Lower Bounds Against Low-Depth Algebraic CircuitsNutan Limaye, Srikanth Srinivasan, Sébastien TavenasFOCS 2021 · 被引用 26 次
- Ideals, determinants, and straightening: proving and using lower bounds for polynomial idealsRobert Andrews, Michael A. ForbesSTOC 2022 · 被引用 6 次
- Demystifying the border of depth-3 algebraic circuitsPranjal Dutta, Prateek Dwivedi, Nitin SaxenaFOCS 2021 · 被引用 6 次
- Radical Sylvester-Gallai Theorem for CubicsRafael Oliveira, Akash Kumar SenguptaFOCS 2022 · 被引用 3 次
- Reconstruction of Depth-3 Arithmetic Circuits with Constant Top Fan-InShubhangi Saraf, Devansh Shringi, Narmada VaradarajanSTOC 2026 · 被引用 2 次
相关 Paper
- 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 次
- Reconstruction of Depth-4 Multilinear CircuitsVishwas Bhargava, Shubhangi Saraf, Ilya VolkovichSODA 2020 · 被引用 5 次
- Strong Algebras and Radical Sylvester-Gallai ConfigurationsRafael Oliveira, Akash Kumar SenguptaSTOC 2024 · 被引用 1 次
- Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum CircuitsNolan J. Coble, Matthew CoudronFOCS 2021 · 被引用 3 次
- Fast Deterministic Chromatic Number under the Asymptotic Rank ConjectureAndreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski 等SODA 2025 · 被引用 1 次
