Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

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

 Title, Booktitle
 Title*: On the Sum of Square Roots of Polynomials and Related Problems Booktitle*: 26th IEEE Conference on Computational Complexity (CCC)

 Event, URLs
 URL of the conference: http://computationalcomplexity.org/Archive/2011/cfp.html URL for downloading the paper: http://www.mpi-inf.mpg.de/~csaha/Sum_sqrroot.pdf Event Address*: San Jose, USA Language: English Event Date* (no longer used): Organization: IEEE Computer Society Technical Committee for Mathematical Foundations of Computing Event Start Date: 8 June 2011 Event End Date: 10 June 2011

 Publisher
 Name*: IEEE Computer Society URL: http://www.computer.org/portal/web/guest/home Address*: Washington, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 292-299 Year*: 2011 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (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_{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}. Keywords: Sum of square roots, arithmetic circuit complexity 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:

@INPROCEEDINGS{KS11,
AUTHOR = {Kayal, Neeraj and Saha, Chandan},
TITLE = {On the Sum of Square Roots of Polynomials and Related Problems},
BOOKTITLE = {26th IEEE Conference on Computational Complexity (CCC)},
PUBLISHER = {IEEE Computer Society},
YEAR = {2011},
ORGANIZATION = {IEEE Computer Society Technical Committee for Mathematical Foundations of Computing},
PAGES = {292--299},