Polynomial identity testing for depth 3 circuits
We study the identity testing problem for depth 3 arithmetic circuits (Sigma Pi Sigma circuit). We give the first deterministic polynomial time identity test for Sigma Pi Sigma circuits with bounded top fanin. We also show that the rank of a minimal and simple Sigma Pi Sigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman (STOC 2001) and Dvir-Shpilka (STOC 2005).
identity testing depth of circuits chinese remaindering rings