REPORTS > DETAIL:

### Paper:

TR05-150 | 5th December 2005 00:00

#### Polynomial Identity Testing for Depth 3 Circuits

TR05-150
Authors: Neeraj Kayal, Nitin Saxena
Publication: 8th December 2005 14:35
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint