{"id":"arxiv/2606.25118","url":"https://arxiv.org/abs/2606.25118","tags":["math.OC","cs.CC","math.AG"],"score":0,"title":"Sums of squares in polynomial time","domain":"math.OC","source":"arxiv","authors":["Nikolas Gärtner","Victor Magron","Frank Vallentin"],"reviews":0,"subject":"math.OC","summary":"In this paper, we analyze the bit complexity of deciding whether a given polynomial can be represented as a sum of squares of polynomials. We show that the weak membership problem for the sum-of-squares cone lies in $\\mathrm{P}$. Furthermore, we give a polynomial-time algorithm which computes, for a given polynomial and positive parameter $ε$, an $ε$-relaxed closest sum-of-squares polynomial.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-23","reactions":{}}