@article{KayaSaha:ACM-TCT:2012,
    Abstract = {The sum of square roots over integers problem is the task of deciding the sign of a nonzero sum, S = ∑i=1n δi · √ai, where δi ∈ {+1, −1} and ai's are positive integers that are upper bounded 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 ≠ 0. We study a formulation of this problem over polynomials. Given an expression S = ∑i=1n ci · √fi(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)≠0 for all i, is it true that the minimum exponent of x that 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 nonzero S = ∑i=1n δi · √ai is lower bounded as ∣S∣ ≥ 1/X(n·d)O(1). The constant in O(1), 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 et al. [2009] and Koiran and Perifel [2007].},
    Address = {New York, NY, USA},
    Author = {Kayal, Neeraj and Saha, Chandan},
    File = {On the sum of square roots of polynomials and related problems - Sum20of20Square20Roots20ToCT.pdf},
    ISSN = {1942-3454},
    Journal = {ACM Trans. Comput. Theory},
    Keywords = {arithmetic circuits, polynomials, Sum of square roots},
    Month = {nov},
    Number = {4},
    Publisher = {Association for Computing Machinery},
    Title = {On the Sum of Square Roots of Polynomials and Related Problems},
    URL = {https://doi.org/10.1145/2382559.2382560},
    Volume = {4},
    Year = {2012},
    articleno = {9},
    date-added = {2022-06-29 12:21:59 +0200},
    date-modified = {2023-08-24 15:46:20 +0200},
    file-2 = {On the Sum of Square Roots of Polynomials and Related Problems - kayal2012 - a.pdf},
    issue_date = {November 2012},
    numpages = {15},
    doi = {10.1145/2382559.2382560}
}

@article{KayaSaha:ACM-TCT:2012, Abstract = {The sum of square roots over integers problem is the task of deciding the sign of a nonzero sum, S = ∑i=1n δi · √ai, where δi ∈ {+1, −1} and ai's are positive integers that are upper bounded 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 ≠ 0. We study a formulation of this problem over polynomials. Given an expression S = ∑i=1n ci · √fi(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)≠0 for all i, is it true that the minimum exponent of x that 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 nonzero S = ∑i=1n δi · √ai is lower bounded as ∣S∣ ≥ 1/X(n·d)O(1). The constant in O(1), 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 et al. [2009] and Koiran and Perifel [2007].}, Address = {New York, NY, USA}, Author = {Kayal, Neeraj and Saha, Chandan}, File = {On the sum of square roots of polynomials and related problems - Sum20of20Square20Roots20ToCT.pdf}, ISSN = {1942-3454}, Journal = {ACM Trans. Comput. Theory}, Keywords = {arithmetic circuits, polynomials, Sum of square roots}, Month = {nov}, Number = {4}, Publisher = {Association for Computing Machinery}, Title = {On the Sum of Square Roots of Polynomials and Related Problems}, URL = {https://doi.org/10.1145/2382559.2382560}, Volume = {4}, Year = {2012}, articleno = {9}, date-added = {2022-06-29 12:21:59 +0200}, date-modified = {2023-08-24 15:46:20 +0200}, file-2 = {On the Sum of Square Roots of Polynomials and Related Problems - kayal2012 - a.pdf}, issue_date = {November 2012}, numpages = {15}, doi = {10.1145/2382559.2382560} }