Abstract
Is it possible to solve the n-variable, degree-d SOS relaxation in n^{O(d)} time? I don't know. Approximately? I don't know. In the Archimedean case? I don't know.
What about telling whether a multivariate polynomial with rational coefficients is a sum of squares: is this in P? I don't know. Is it in NP? I don't know. Is it in PSPACE? Yes, although it's nontrivial.
I'll discuss some of these issues, including recent positive results.