

(LaTeX) Abstract: 
The sum of square roots problem over integers is the task of
deciding the sign of a \emph{nonzero} 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{nonzero} $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 
