Skip to main content

Frank Vallentin: On the computational complexity of SOS

Date of publication: 7. 10. 2026
Mathematics colloquium
Wednesday
14
October
Time:
16:15 - 17:00
Location:
FMF, Jadranska 21, predavalnica 1.01

On the computational complexity of SOS

Frank Vallentin University of Cologne

Let $p$ be a real polynomial in $n$ variables of even degree $2d$. A fundamental computational task, with applications in optimization and real algebraic geometry, is to decide whether $p$ can be written as a sum of squares of polynomials. That is, whether there exist polynomials $q_1, \ldots, q_m$ such that $p = q_1^2 + q_2^2 + \cdots + q_m^2$. In this talk, I will discuss the computational complexity of this question.

(based on joint work with Nikolas G\" artner and Victor Magron, https://arxiv.org/abs/2606.25118}

Attachments