I have been reading a bit about the sum-of-squares method (SOS) from the survey of Barak & Steurer and the lecture notes of Barak. In both cases they sweep issues of numerical accuracy under the rug.From my (admittedly limited) understanding of the method, the following should be true:Given any system of polynomial equalities $E$ over real-valued variables $x \in \mathbb{R}^n$, where all parameters are $O(1)$ ($n$, $|E|$, and degree of each constraint), the degree-$2n$ ($=O(1)$) SOS method finds a satisfying assignment of the variables or proves none exists in $O(1)$ time.  My first question is whether the above claim is true (is there a naive argument that doesn't use SOS to solve this?). The second question is where numerical accuracy fits in. If I want to get an assignment that satisfies all constraints to within additive $\varepsilon$ accuracy, how does the runtime depend on $1/\varepsilon$? In particular, is it polynomial?The motivation for this is to, say, apply a divide-and-conquer approach on a large system until the base case is an $O(1)$-size system.EDIT: From Barak-Steurer, it appears that the degree $l$ sum-of-squares algorithm on p.9 (and the paragraphs leading up to it) all define problems for solutions over $\mathbb{R}$, and in fact the definition of a pseudo-distribution in section 2.2 is over $\mathbb{R}$. Now I am seeing from Lemma 2.2, however, that one is not guaranteed a solution/refutation at degree $2n$ without binary variables. So I can refine my question a little bit. If your variables are not binary, the worry is that the sequence of outputs $\varphi^{(l)}$ is not finite (maybe not even monotonic increasing?). So the question is: is $\varphi^{(l)}$ still increasing? And if so, how far you have to go to get additive accuracy $\varepsilon$? Though this likely does not change anything, I happen to know my system is satisfiable (there is no refutation of any degree), so I am really just concerned about how large $l$ needs to be. Finally, I am interested in a theoretical solution, not a numerical solver.
Numerical precision in sum-of-squares method?
optimization;sum of squares
Here is Boaz Barak's comment on the issue:We do sweep numerical accuracy under the rug -- the more traditional SOS literature of Parrilo, Lasserre etc.. deals with these issues (e.g., see Monique Laurent's surveys and the references therein). It is known that that the hierarchy is monotone (it's not hard to see that a degree $l$ psuedo-distribution is in particular a degree $l-1$ one), and that it will converge in finite degree for any fixed set of equations (this is the Positivstellensatz). The exact degree could vary. Generally, if all the coefficients of the polynomials are bounded and you are trying to distinguish between the case that there is a solution and the case that in any assignment one of the equations is off by $\epsilon$, then one could discretize this to a $\delta$-net for $\delta$ related to the number of variables, degree of equations, and $\epsilon$, and then (assuming the net is sufficiently nice and cube like) the degree required should be roughly log the size of the net.