TR05-150 Authors: Neeraj Kayal, Nitin Saxena

Publication: 8th December 2005 14:35

Downloads: 1853

Keywords:

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em 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 \cite{ks01} and Dvir-Shpilka \cite{ds05}.