Proof for Upper Bound of Sum of Square Roots Problem
Here is a rather sloppy proof sketch. Let $S = \sum_{i=1}^n \delta_i \sqrt{a_i}$ where $\delta_i \in \{\pm 1\}$. This is an algebraic number of degree at most $2^n$ and height at most $H = (max(a_i))^{n}$. Now it is easy to check if $S = 0$ (can be done even in $TC^0$ -- see this).If $S \neq 0$ then it is bounded away from $0$ by a quantity (because it is an algebraic number and hence is a non-zero root of a univariate polynomial) that is a function of the degree and height of the minimal polynomial of $S$. Unfortunately, the dependence on the degree is exponential in the number of square roots (and if the $a_i$'s are distinct primes, this degree bound is even tight, though that case of sign evaluation is easy to handle). The precision needed is hence exponential in the number of square roots, which is $2^n$-bits for $S$. It now suffices to truncate each of the $\sqrt{a_i}$ to say $2^{10n}$ bits to ensure the sign is guaranteed to be correct. This is easily done via polynomially many steps of Newton iteration). Now it is down to checking if the sum is positive, which is just addition and hence linear in the number of bits in the summands. Notice that this computation is in Polynomial time on a BSS machine. Also notice that we are not doing any computation directly with the minimal polynomial of $S$ itself, which could have huge coefficients and look ugly, we just use it to reason about the precision to which we need to truncate the square roots. For more details, check Tiwari's paper.