MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://computationalcomplexity.org/Archive/2011/cfp.html
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {San Jose, USA},
 MONTH = {June},
}

Entry last modified by Uwe Brahm, 05/22/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Chandan Saha		Created
01/17/2013 07:26:18 AM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Uwe Brahm
Chandan Saha
Chandan Saha
Chandan Saha
Chandan Saha		Edit Dates
01-02-2013 03:07:39 PM
01/18/2013 05:20:01 AM
01/17/2013 07:43:02 AM
01/17/2013 07:42:15 AM
01/17/2013 07:29:03 AM