Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Nitin Saxena · Computational Complexity · 2006
We study the identity testing problem for depth 3 arithmetic circuits (SigmaPiSigma circuit). We give the first deterministic polynomial time identity test for SigmaPiSigma circuits with bounded top fanin. We also show that the rank of a minimal and simple SigmaPiSigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman (2001) and Dvir-Shpilka (2005)