Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-150 | 5th December 2005 00:00

Polynomial Identity Testing for Depth 3 Circuits

RSS-Feed




TR05-150
Authors: Neeraj Kayal, Nitin Saxena
Publication: 8th December 2005 14:35
Downloads: 3212
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