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 Library locked




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, Abstract, ©

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},
ADDRESS = {New York, NY},
ISBN = {1942-3454},
DOI = {10.1145/2382559.2382560},
}


Entry last modified by Anja Becker, 02/06/2013
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
[Library]
Created
01/17/2013 07:40:15 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Anja Becker
Uwe Brahm
Chandan Saha
Chandan Saha
Chandan Saha
Edit Dates
06.02.2013 13:13:03
01-02-2013 02:46:40 PM
01/18/2013 05:17:06 AM
01/18/2013 05:16:24 AM
01/17/2013 07:41:30 AM