English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

On the Sum of Square Roots of Polynomials and Related Problems

MPS-Authors
/persons/resource/persons45333

Saha,  Chandan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Kayal, N., & Saha, C. (2012). On the Sum of Square Roots of Polynomials and Related Problems. The ACM Transactions on Computation Theory, 4(4), 9:1-9:15. doi:10.1145/2382559.2382560.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-BDEC-0
Abstract
The sum of square roots problem over integers is the task of deciding the sign of a \emphnon-zero} sum, S = \sum_{i=1}^{n}{δ_i ⋅ \sqrt{a_i}}, where δ_i \in { +1, -1} and a_i's are positive integers that are upper bounded by N (say). A fundamental open question in numerical analysis and computational geometry is whether \abs{S} ≥q 1/2^{(n ⋅ \log N)^{O(1)}} when S \neq 0. We study 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 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 a_i is of the form, a_i = X^{d_i} + b_{i 1} X^{d_i - 1} + \ldots + b_{i d_i}, \hspace{0.1in} d_i > 0, where X is a positive real number and b_{i j}'s are integers. Let B = \max ({\abs{b_{i j}}}_{i, j}, 1) and d = \max_i{d_i}. If X > (B+1)^{(n ⋅ d)^{O(1)}} then a \emph{non-zero} S = \sum_{i=1}^{n}{δ_i ⋅ \sqrt{a_i}} is lower bounded as \abs{S} ≥q 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(\vecx) and integer d, is the degree of f(\vecx) less than or equal to d? We give a \mathsf{coRP}^{\mathsf{PP}-algorithm for this problem, improving previous results of Allender, Bürgisser, Kjeldgaard-Pedersen and Miltersen (2009), and Koiran and Perifel (2007).