Here is a proposition and a conjecture, which together would establish an algorithm for determining whether a multilinear $f$ has a root.

**Proposition**

Let $c$ be the coefficient of $x_1x_2\cdots x_t$ in a multilinear $f(x_1,\ldots,x_t)$.

Let $k$ be the sum of the absolute values of the coefficients in $f$.

If $c>0$, then $f$ has roots iff it has roots where some $x_i$ has $|x_i|<k/c$.

*Proof:* Suppose all the $x_i$ have $|x_i|\ge k/c$. Let $P = x_1x_2\cdots x_t$. We rewrite the equation $f(x_1,\ldots,x_t)=0$ so the left side has the term with $P$, and the right side has everything else. The left side is $cP$. On the right side, each product of variables is at most $P/(k/c)$, since each of those products is missing at least one factor that goes into $P$. Taking absolute values gives $c|P| \le (k-c)|P|/(k/c)$, which is impossible.

**Conjecture**

Let $c$ be the coefficient of $x_1x_2\cdots x_t$ in a multilinear $f(x_1,\ldots,x_t)$.

If $c=0$, then $f$ has roots iff its constant coefficient is divisible by the gcd of the non-constant coefficients.

*Comments:* This clearly holds if $f$ is linear, e.g. $f(x,y,z)=6x + 10y+ 15z + 7$ or $6x+10y+30z+7$. For non-linear but still multilinear $f$, non-trivial examples may look like $f(x,y,z)=xy+yz+zx+x-5$. I have done some numerical investigations of cases like this; we are looking for solutions to a multilinear Diophantine equation in at least three unknowns, and my conjecture is that it always has a root.


**Algorithm conditional on the above**

If $t=1$ it is trivial to determine if $f$ has a root.

If $t>1$ and $c=0$, we can determine whether $f$ has a root according to the above conjecture.

If $t>1$ and $c\neq 0$, let $d=\lfloor k/|c|\rfloor$. Then we can determine whether $f$ has a root by substituting the integers in $[-d,d]$ for each variable. Specifically, we test whether $f(-d,x_2,\ldots,x_t)$ has a root, and whether $f(-d+1,x_2,\ldots,x_t)$ has a root, making all possible substitutions until testing whether $f(x_1,x_2,\ldots,d)$ has a root. By the above proposition, $f$ has a root iff one of these polynomials with fewer variables has a root.

*Summary:* We use real inequalities if $f$ has a term with all the variables, and divisibility otherwise, and that may be enough.