Name
Abstract | ||
|---|---|---|
The sum of square roots problem over integers is the task of deciding the sign of a non-zero sum, S = \sum_{i=1}^{n}{\delta_i \cdot \sqrt{a_i}}, where\delta_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} \geq 1/2^{(n \cdot \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 \cdot \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 \cdot 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_{i,j}\{\abs{b_{i j}}\} and d = \max_i\{d_i\}$. If $X (B+1)^{(n \cdot d)^{O(1)}} then a \emph{non-zero} S = \sum_{i=1}^{n}{\delta_i \cdot \sqrt{a_i}} is lower bounded as \abs{S} \geq 1/X^{(n \cdot 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 \cite{ABKM09} and \cite{KP07}. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2382559.2382560 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
square roots problem,numerical analysis,nonzero sum,integer a_i,nonzero coefficient,question affirmatively,i d_i,non-zero sum,positive real number,i j,positive integer,related problems,general problem,fundamental open question,integers problem,square roots,integers,upper bound,indexes,power series,sum of squares,taylor series,indexation,polynomials,arithmetic circuit complexity,computational geometry | Journal | 4 |
Issue | ISSN | ISBN |
4 | 1093-0159 E-ISBN : 978-0-7695-4411-3 | 978-0-7695-4411-3 |
Citations | PageRank | References |
6 | 0.44 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Chandan Saha | 2 | 227 | 16.91 |