DETERMINISTIC POLYNOMIAL IDENTITY TESTS FOR MULTILINEAR BOUNDED-READ FORMULAE

作者：Anderson Matthew^*; van Melkebeek Dieter; Volkovich Ilya

来源：Computational Complexity, 2015, 24(4): 695-776.

DOI：10.1007/s00037-015-0097-4

• Derandomization
• identity testing
• arithmetic circuits
• bounded-depth circuits

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. Our algorithm runs in time s(O(1)) center dot n(kO(k)), where s denotes the size of the formula, n denotes the number of variables, and k bounds the number of occurrences of each variable. 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 time n(kO(k)+O(k log n)) in general, and time n(kO(k2)+O(kD)) for depth D. 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 formulae.

• 出版日期2015-12