Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

被引：7

作者：

Anderson, Matthew ^{[1
]}

Forbes, Michael A. ^{[2
]}

Saptharishi, Ramprasad ^{[3
]}

Shpilka, Amir ^{[3
]}

Volk, Ben Lee ^{[3
]}

机构：

[1] Union Coll, Dept Comp Sci, Schenectady, NY 12308 USA

[2] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

[3] Tel Aviv Univ, Dept Comp Sci, Tel Aviv, Israel

来源：

31ST CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2016) | 2016年 / 50卷

关键词：

Algebraic Complexity; Lower Bounds; Derandomization; Polynomial Identity Testing; PSEUDORANDOM GENERATORS; ARITHMETIC CIRCUITS; DEPTH; 4; COMPUTATION; CHASM;

D O I：

10.4230/LIPIcs.CCC.2016.30

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k (k)) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box xsubexponential-time PIT algorithm. The algorithm runs in time 2 (1 1/2k-i) and needs white box access only to know the order in which the variables appear in the ABP.

引用

页数：25

共 28 条

[21] Linear codes are hard for oblivious read-once parity branching programs
Jukna, S
INFORMATION PROCESSING LETTERS, 1999, 69 (06) : 267 - 269
[22] Diagonal circuit identity testing and lower bounds
Saxena, Nitin
AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, PROCEEDINGS, 2008, 5125 : 60 - 71
[23] Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing
Kumar, Mrinal
Saraf, Shubhangi
31ST CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2016), 2016, 50
[24] On the nonapproximability of Boolean functions by OBDDs and read-k-times branching programs
Bollig, B
Sauerhoff, M
Wegener, I
INFORMATION AND COMPUTATION, 2002, 178 (01) : 263 - 278
[25] A lower bound for integer multiplication on randomized ordered read-once branching programs
Ablayev, F
Karpinski, M
INFORMATION AND COMPUTATION, 2003, 186 (01) : 78 - 89
[26] On the non-approximability of boolean functions by OBDDs and read-k-times branching programs
Bollig, B
Sauerhoff, M
Wegener, I
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, : 172 - 183
[27] On the size of randomized OBDDs and read-once branching programs for k-stable functions
Sauerhoff, M
COMPUTATIONAL COMPLEXITY, 2001, 10 (02) : 155 - 178
[28] Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
Bollig, Beate
Waack, Stephan
Woelfel, Philipp
THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) : 86 - 99

← 1 2 3 →