Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-189 | 8th December 2010 22:00

On the Sum of Square Roots of Polynomials and related problems


Authors: Neeraj Kayal, Chandan Saha
Publication: 9th December 2010 19:35
Downloads: 2823


The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \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 $|S| \geq 1/2^{(n.\log N)^{O(1)}}$. We study a formulation of this problem over polynomials: Given an expression S = $\Sigma_{i=1}^{n}{c_i}.$ \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.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} + ... + b_{i d_i}, (d_i > 0)$, where $X$ is a positive real number and $b_{i j}$'s are integers. Let $B = \max_{i,j}{|b_{i j}|}$ and $d = \max_i{d_i}$. If $X > (B+1)^{(n.d)^{O(1)}}$ then a nonzero $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$} is lower bounded as $|S| \geq 1/X^{(n.d)^{O(1)}}$.

We then consider the following more general problem: given an arithmetic circuit computing a multivariate polynomial $f(X)$ and integer $d$, is the degree of $f(X)$ less than or equal to $d$? We give a $coRP^{PP}$-algorithm for this problem, improving previous results of Allender, B\"{u}rgisser, Kjeldgaard-Pedersen and Miltersen (2009), and Koiran and Perifel (2007).

ISSN 1433-8092 | Imprint