We study the identity testing problem for depth 3 arithmetic circuits (Sum-Product-Sum circuits). We give the first deterministic polynomial time identity test for Sum-Product-Sum circuits with bounded top fanin. We also show that the rank of a minimal and simple Sum-Product-Sum 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).

}, author = {Neeraj Kayal and Nitin Saxena}, journal = {Computational Complexity}, month = {July}, number = {2}, pages = {115-138}, publisher = {Springer Verlag}, title = {Polynomial Identity Testing for Depth 3 Circuits}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=102436}, volume = {16}, year = {2007}, }