Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

被引：18

作者：

Anderson, Matthew ^{[1
]}

van Melkebeek, Dieter ^{[1
]}

Volkovich, Ilya ^{[2
]}

机构：

[1] Univ Wisconsin, Dept Comp Sci, Madison, WI 53706 USA

[2] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

2011 IEEE 26TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC) | 2011年

基金：

欧洲研究理事会; 美国国家科学基金会;

关键词：

arithmetic circuit; bounded-depth circuit; derandomization; polynomial identity testing;

D O I：

10.1109/CCC.2011.18

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Before our work no subexponential-time deterministic algorithm was known for this class of formulae. We also present a deterministic algorithm that works in a blackbox fashion and runs in quasi-polynomial time in general, and polynomial time for constant depth. Finally, we extend our results and allow the inputs to be replaced with sparse polynomials. Our results encompass recent deterministic identity tests for sums of a constant number of read-once formulae, and for multilinear depth-four circuits.

引用

页码：273 / 282

页数：10

共 26 条

[1] AARONSON S, 2010, 105 EL C COMP COMPL
[2] Agrawal M, 2005, LECT NOTES COMPUT SC, V3821, P92, DOI 10.1007/11590156_6
[3] On derandomizing tests for certain polynomial identities
Agrawal, M
[J]. 18TH IEEE ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2003, : 355 - 359
[4] Primality and identity testing via Chinese remaindering
Agrawal, M
Biswas, S
[J]. JOURNAL OF THE ACM, 2003, 50 (04) : 429 - 443
[5] ANDERSON M, 2010, 188 EL C COMP COMPL
[6] [Anonymous], 1979, FCT
[7] The Ideal Membership Problem and polynomial identity testing
Arvind, V.
Mukhopadhyay, Partha
[J]. INFORMATION AND COMPUTATION, 2010, 208 (04) : 351 - 363
[8] Ben-Or M., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P301, DOI 10.1145/62212.62241
[9] Deterministically testing sparse polynomial identities of unbounded degree
Blaeser, Markus
Hardt, Moritz
Lipton, Richard J.
Vishnoi, Nisheeth K.
[J]. INFORMATION PROCESSING LETTERS, 2009, 109 (03) : 187 - 192
[10] PROBABILISTIC REMARK ON ALGEBRAIC PROGRAM TESTING
DEMILLO, RA
LIPTON, RJ
[J]. INFORMATION PROCESSING LETTERS, 1978, 7 (04) : 193 - 195

← 1 2 3 →