Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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:




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
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)
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