Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor(s)
 Author(s): Kayal, Neeraj Saha, Chandan dblp dblp Not MPG Author(s): Kayal, Neeraj
 BibTeX cite key*: KS12

 Title
 Title*: On the Sum of Square Roots of Polynomials and Related Problems

 Journal
 Journal Title*: The ACM Transactions on Computation Theory Journal's URL: http://toct.acm.org/ Download URL for the article: http://doi.acm.org/10.1145/2382559.2382560 Language: English

 Publisher
 Publisher's Name: ACM Publisher's URL: Publisher's Address: New York, NY ISSN: 1942-3454

 Vol, No, pp, Date
 Volume*: 4 Number: 4 Publishing Date: 2012 Pages*: 9:1-9:15 Number of VG Pages: Page Start: 9:1-9:15 Page End: Sequence Number: 9 DOI: 10.1145/2382559.2382560

 Note: (LaTeX) Abstract: The sum of square roots problem over integers is the task of deciding the sign of a \emph{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 (\{\abs{b_{i j}}\}_{i, j}, 1)$ 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 Allender, B\"{u}rgisser, Kjeldgaard-Pedersen and Miltersen ($2009$), and Koiran and Perifel ($2007$). URL for the Abstract: Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Internal

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{KS12,
AUTHOR = {Kayal, Neeraj and Saha, Chandan},
TITLE = {On the Sum of Square Roots of Polynomials and Related Problems},
JOURNAL = {The ACM Transactions on Computation Theory},
PUBLISHER = {ACM},
YEAR = {2012},
NUMBER = {4},
VOLUME = {4},
PAGES = {9:1--9:15},