![Bridging Continuous and Discrete Optimization_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Bridging%20Continuous%20and%20Discrete%20Optimization_hi-res.png.jpg?itok=b7fmT0eV)
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.