ECCC-Report TR05-150https://eccc.weizmann.ac.il/report/2005/150Comments and Revisions published for TR05-150en-usThu, 08 Dec 2005 14:35:33 +0200
Paper TR05-150
| Polynomial Identity Testing for Depth 3 Circuits |
Neeraj Kayal,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2005/150We 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}.
Thu, 08 Dec 2005 14:35:33 +0200https://eccc.weizmann.ac.il/report/2005/150