Seminar by Chandan Saha
On the Sum of Square Roots of Polynomials and Related Problems
Chandan Saha
Max-Planck-Institut fur Informatik, Saarbrucken,
Date: Wednesday, October 19th, 2011
Time: 5:15 PM
Venue: CS101.Abstract:
The sum of square roots problem is the task of deciding the sign of a non-zero sum, S = sum_{i=1}^{n}{e_i . sqrt{a_i}}, where e_i in { +1, -1} and a_i's are positive integers less than N. It was posed as a fundamental open problem by Garey, Graham and Johnson (1976) in connection with the Euclidean travelling salesman problem, which is not known to be in the complexity class NP unless `relative' to the sum of square roots problem.
An important open question in numerical analysis and computational geometry is whether in the sum S, it is sufficient to compute the square roots of the ai's to poly(n,log N) bits of precision in order to decide the sign of S. We have studied a formulation of this problem over polynomials: Given an expression S = sum_{i=1}^{n}{c_i . sqrt{f_i(x)}}, where c_i's belong to a field of characteristic 0 and f_i's are univariate polynomials with degree bounded by d (and f_i(0) neq 0 for all i), is it true that the minimum exponent of x which has a non-zero coefficient in the power series S is upper bounded by poly(n,d), unless S=0? We answer this question affirmatively. Further, we show that using this result over polynomials we can settle (positively) the sum of square roots problem for an interesting class of integers that we call the `polynomial numbers'.
We then consider the following more general problem: given an arithmetic circuit computing a multivariate polynomial f and also given an integer d, is the degree of f less than or equal to d? We give a {coRP}^{PP}-algorithm for this problem, improving upon previous results.
This is a joint work with Neeraj Kayal.