## Computing rational radical sums in uniform TC^{0}

*Paul Hunter*, *Patricia Bouyer*, *Nicolas Markey*, *Joël
Ouaknine*, and *James Worrell*
A fundamental problem in numerical computation and computational
geometry is to determine the sign of arithmetic expressions in
radicals. Here we consider the simpler problem of deciding whether
∑_{i=1..m}
*C*_{i}A_{i}^{Xi}
is zero for given rational numbers *A*_{i},
*C*_{i}, *X*_{i}.
It has been known for almost twenty years that this can be decided in
polynomial time [2]. In this paper we improve this result by showing
membership in uniform TC^{0}. This requires several
significant departures from Blömer's polynomial-time algorithm as
the latter crucially relies on primitives, such as gcd computation and
binary search, that are not known to be in TC^{0}.

*Proceedings of FSTTCS 10*, LIPICS 8, 2010. 9 pages.

PDF
© 2010 Patricia Bouyer, Paul Hunter, Nicolas Markey, Joël
Ouaknine, and James Worrell.

Imprint / Data Protection