Title :
Polynomial identity testing for depth 3 circuits
Author :
Kayal, Neeraj ; Saxena, Nitin
Author_Institution :
Dept. of Comput. Sci. & Eng., IIT Kanpur
Abstract :
We study the identity testing problem for depth 3 arithmetic circuits (SigmaPiSigma circuit). We give the first deterministic polynomial time identity test for SigmaPiSigma circuits with bounded top fanin. We also show that the rank of a minimal and simple SigmaPiSigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman (2001) and Dvir-Shpilka (2005)
Keywords :
circuit complexity; digital arithmetic; SigmaPiSigma circuits; bounded top fanin; depth three arithmetic circuits; deterministic polynomial time identity test; polynomial identity testing; Arithmetic; Circuit testing; Complexity theory; Computational complexity; Polynomials; Upper bound;
Conference_Titel :
Computational Complexity, 2006. CCC 2006. Twenty-First Annual IEEE Conference on
Conference_Location :
Prague
Print_ISBN :
0-7695-2596-2
DOI :
10.1109/CCC.2006.34
