Computing Rational Radical Sums in Uniform TC0

Conference item

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=1m CiAiXi is zero for given rational numbers Ai, Ci, Xi. 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 TC0. 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 TC0. © Patricia Bouyer, Paul Hunter, Nicolas Markey, Joël Ouaknine, James Worrell.

Authors: Hunter, P; Bouyer, P; Markey, N; Ouaknine, J; Worrell, J

• Publication status: Published
• Host title: IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010)
• Volume: 8
• Pages: 308-316
• Publication date: 2010-01-01
• DOI: 10.4230/LIPIcs.FSTTCS.2010.308
• ISSN: 1868-8969
• ISBN: 9783939897231
• Keywords: Sum of square roots; Threshold circuits; Complexity