A signed-gap decision criterion for accurate polynomial evaluation

The manuscript gives a finite criterion for the existence of accurate
evaluation algorithms for real polynomials in the constant-free, independently
rounded arithmetic model. For each ordering of the input magnitudes and each
choice of their signs, the inputs are written as signed cumulative sums of
nonnegative gaps and the polynomial is expanded in these gaps; the criterion
requires that the polynomial obtained by taking the absolute values of its
coefficients be bounded by a constant times the absolute value of the
polynomial itself on the entire nonnegative orthant. Necessity is proved by
constructing a separated execution of an arbitrary finite branching program and
replaying it under multiplicative gap perturbations while holding every rounded
value fixed; polynomial interpolation then yields coefficient domination.
Sufficiency follows from direct evaluation in gap coordinates. The criterion is
a finite collection of first-order sentences over the reals, so real quantifier
elimination decides it. Stored values, exact negation, equality branches,
nonhomogeneous polynomials and boundary points are included.