Title | ||
---|---|---|
Polynomial time deterministic identity testing algorithm for Σ[3]ΠΣΠ[2] circuits via Edelstein–Kelly type theorem for quadratic polynomials |
Abstract | ||
---|---|---|
ABSTRACTIn this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS13] and Gupta [Gupta14], 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. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1145/3406325.3451013 | ACM Symposium on Theory of Computing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peleg Shir | 1 | 0 | 0.34 |
Amir Shpilka | 2 | 1095 | 64.27 |