Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Polynomial Identity Testing for Depth 3 Circuits

Neeraj Kayal and Nitin Saxena

Abstract

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

Details

Publication typeArticle
Published inComputational Complexity
URLhttp://eccc.hpi-web.de/report/2005/150/
Pages115-138
Volume16
Number2
PublisherSpringer Verlag
> Publications > Polynomial Identity Testing for Depth 3 Circuits