Arithmetic Circuits: A Chasm at Depth Four

被引：139

作者：

Agrawal, Manindra ^{[1
]}

Vinay, V. ^{[2
,3
]}

机构：

[1] Indian Inst Technol, Kanpur 208016, Uttar Pradesh, India

[2] Chennai Math Inst, Madras, Tamil Nadu, India

[3] Geodesic Informat Syst Ltd, Bangalore, Karnataka, India

来源：

PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2008年

关键词：

D O I：

10.1109/FOCS.2008.32

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization. of Identity Testing problem for depth four circuits with multiplication gates of small fanin implies a nearly complete derandomization of general Identity Testing.

引用

页码：67 / +

页数：3

共 25 条

[1]

Agrawal M., 2005, P FST TCS, P96

[2] Non-commutative arithmetic circuits: depth reduction and size lower bounds [J].

Allender, E ;

Jiao, J ;

Mahajan, M ;

Vinay, V .

THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :47-86

[3] A TAXONOMY OF PROBLEMS WITH FAST PARALLEL ALGORITHMS [J].

COOK, SA .

INFORMATION AND CONTROL, 1985, 64 (1-3) :2-22

[4]

DAMM C, 1991, 8 HUMB U BERL

[5]

Dvir Z, 2008, ACM S THEORY COMPUT, P741

[6] Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields [J].

Grigoriev, D ;

Razborov, A .

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2000, 10 (06) :465-487

[7] SOME EXACT COMPLEXITY RESULTS FOR STRAIGHT-LINE COMPUTATIONS OVER SEMIRINGS [J].

JERRUM, M ;

SNIR, M .

JOURNAL OF THE ACM, 1982, 29 (03) :874-897

[8] Derandomizing polynomial identity tests means proving circuit lower bounds [J].

Kabanets, V ;

Impagliazzo, R .

COMPUTATIONAL COMPLEXITY, 2004, 13 (1-2) :1-46

[9]

KALTOFEN ERICH, 1989, Randomness and Computation, P375

[10] Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in [J].

Karnin, Zohar S. ;

Shpilka, Arnir .

TWENTY-THIRD ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2008, :280-291

← 1 2 3 →