- 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
*s*^{O(1)}*n*^{k}^{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 *n*^{k}^{O(*k*)} + O(*k* log *n*)
in general, and time
*n*^{k}^{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.