Polynomial identity testing for depth 3 circuits

被引：60

作者：

Kayal, Neeraj

Saxena, Nitin

机构：

[1] Inst Adv Study, Princeton, NJ 08540 USA

[2] Ctr Wiskunde & Informat, NL-1098 SJ Amsterdam, Netherlands

来源：

COMPUTATIONAL COMPLEXITY | 2007年 / 16卷 / 02期

关键词：

identity testing; depth of circuits; Chinese remaindering; rings;

D O I：

10.1007/s00037-007-0226-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 (STOC 2001) and Dvir-Shpilka (STOC 2005).

引用

页码：115 / 138

页数：24

共 20 条

[1] Crosstalk and microlens study in a color CMOS image sensor [J].