Abstract | ||
---|---|---|
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)}\\cdot n^{k^{O(k)}}}$$sO(1)·nkO(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^{k^{O(k)} + O(k \\log n)}}$$nkO(k)+O(klogn) in general, and time $${n^{k^{O(k^2)} + O(kD)}}$$nkO(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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s00037-015-0097-4 | Computational Complexity |
Keywords | Field | DocType |
Derandomization, identity testing, arithmetic circuits, bounded-depth circuits, 12Y05, 68Q25 | Discrete mathematics,Binary logarithm,Arithmetic circuits,Combinatorics,Polynomial,Identity testing,Multilinear polynomial,Deterministic algorithm,Multilinear map,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
24 | 4 | 1420-8954 |
Citations | PageRank | References |
5 | 0.44 | 33 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthew Anderson | 1 | 33 | 2.67 |
Dieter van Melkebeek | 2 | 487 | 32.80 |
Ilya Volkovich | 3 | 145 | 8.64 |