- Authors: M. Anderson, D. van Melkebeek, and I. Volkovich.
- Reference: Computational Complexity, 24: 695-776, 2015.
- Earlier version:
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
sO(1)nk^{O(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 nk^{O(k)} + O(k log n)
in general, and time
nk^{O(k*k)} + 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.
