Computing rational radical sums in uniform TC⁰

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_iA_i^X_i 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⁰. 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⁰.

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

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