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).

PDF file

In  Computational Complexity

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details