loading...
Polynomial Identity Testing for Depth 3 Circuits
Prague, Czech Republic July 16-July 20
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2006.3421st Annual IEEE Conference on Compu ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Neeraj Kayal, Nitin Saxena, "Polynomial Identity Testing for Depth 3 Circuits," Computational Complexity, Annual IEEE Conference on, pp. 9-17, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.34,
author = {Neeraj Kayal and Nitin Saxena},
title = {Polynomial Identity Testing for Depth 3 Circuits},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {9-17},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.34},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Polynomial Identity Testing for Depth 3 Circuits
SN - 1093-0159
SP9
EP17
A1 - Neeraj Kayal,
A1 - Nitin Saxena,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Neeraj Kayal, IIT Kanpur, India
Nitin Saxena, IIT Kanpur, India
We study the identity testing problem for depth 3 arithmetic circuits (\Sigma\Pi\Sigma circuit). We give the first deterministic polynomial time identity test for \Sigma\Pi\Sigma circuits with bounded top fanin. We also show that the 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 [KS01] and Dvir-Shpilka [DS05].
Citation:
Neeraj Kayal, Nitin Saxena, "Polynomial Identity Testing for Depth 3 Circuits," ccc, pp.9-17, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.