Polynomial time deterministic identity testingalgorithm for Σ^[3]ΠΣΠ^[2] circuits via Edelstein-Kelly type theorem for quadratic polynomials

2020/06/15 by Peleg, Shir, Shpilka, Amir
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2006.08263

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.

Related

• Rank Bounds and PIT for Σ³ ΠΣΠ^d circuits via a non-linear Edelstein-Kelly theorem
• Shallow Circuits with High-Powered Inputs
• Black-box Identity Testing for Low Degree Unmixed ΣΠΣΠ(k) Circuits
• PIT for depth-4 circuits and Sylvester-Gallai conjecture for polynomials
• Diagonal Circuit Identity Testing and Lower Bounds