Polynomial Identity Testing for Depth 3 Circuits

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

depth3_journal.pdf
PDF file

In  Computational Complexity

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details

TypeArticle
URLhttp://eccc.hpi-web.de/report/2005/150/
Pages115-138
Volume16
Number2
> Publications > Polynomial Identity Testing for Depth 3 Circuits