de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

On the Sum of Square Roots of Polynomials and Related Problems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45333

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

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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).