@inproceedings{kayal2011on,
author = {Kayal, Neeraj and Saha, Chandan},
title = {On the Sum of Square Roots of Polynomials and related problems},
booktitle = {Conference on Computational Complexity (CCC)},
year = {2011},
month = {June},
abstract = {The sum of square roots problem over integers is the task of deciding the sign of a non-zero sum, S =Pn i=1 δi ·√ai, where δi ∈ [+1,−1] and ai’s are positive integers that are upperbounded by N (say). A fundamental open question in numerical analysis and computational geometry is whether |S|≥1/2(n·log N)O(1) when S 6= 0. We study a formulation of this problem over polynomials: Given an expression S =Pn i=1 ci ·pfi(x), where ci’s belong to a field of characteristic 0 and fi’s are univariate polynomials with degree bounded by d and fi(0)6= 0 forall i, is it true that the minimum exponent of x which has a nonzero coefficient in the power series S is upper bounded by (n·d)O(1), unless S = 0? We answer this question affirmatively. Further, we show that this result over polynomials can be used to settle (positively) the sum of square roots problem for a special class of integers: Suppose each integer ai is of the form, ai = Xdi + bi1Xdi−1 + ... + bidi, di > 0, where X is a positive real number and bij’s are integers. Let B = max([|bij|]i,j,1) and d = maxi[di]. If X > (B +1)(n·d)O(1) then a non-zero S =Pn i=1 δi ·√ai is lower bounded as |S|≥ 1/X(n·d)O(1). The constant in the O(1) notation, as fixed by our analysis, is roughly 2. We then consider the following more general problem: given an arithmetic circuit computing a multivariate polynomial f(X) and integer d, is the degree of f(X) less than or equal to d? We give a coRPPP-algorithm for this problem, improving previous results of Allender, Bu¨rgisser, Kjeldgaard-Pedersen and Miltersen (2009), and Koiran and Perifel (2007).},
publisher = {IEEE},
url = {http://approjects.co.za/?big=en-us/research/publication/on-the-sum-of-square-roots-of-polynomials-and-related-problems/},
edition = {Conference on Computational Complexity (CCC)},
note = {Invited to ToCT journal},
}