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 ^{[4
]}

Volk, Ben Lee ^{[4
]}

机构：

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

[2] Univ Illinois, Thomas M Siebel Ctr Comp Sci, Dept Comp Sci, 201 North Goodwin Ave, Urbana, IL 61801 USA

[3] Tata Inst Fundamental Res, Sch Technol & Comp Sci, Dr Homi Bhabha Rd, Bombay 400005, Maharashtra, India

[4] Tel Aviv Univ, Sch Comp Sci, Schreiber Bldg,POB 39040, IL-6997801 Tel Aviv, Israel

来源：

ACM TRANSACTIONS ON COMPUTATION THEORY | 2018年 / 10卷 / 01期

关键词：

Algebraic complexity theory; algebraic circuits; polynomial identity testing; lower bounds;

D O I：

10.1145/3170709

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ABP). In this work, we give an exponential lower bound of exp(n/k(O(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 subexponential-time PIT algorithm. The algorithm runs in time 2 (O) over tilde (n(1-1/2k-1)) and needs white box access only to know the order in which the variables appear in the ABP.

引用

页数：30

共 27 条

[21] Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order
Forbes, Michael A.
Saptharishi, Ramprasad
Shpilka, Amir
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 867 - 875
[22] 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
[23] 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
[24] 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
[25] 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
[26] On the size of randomized OBDDs and read-once branching programs for k-stable functions
Sauerhoff, M
COMPUTATIONAL COMPLEXITY, 2001, 10 (02) : 155 - 178
[27] 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 →