Sums of squares in polynomial time
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.25118
curl -X POST /api/v1/records/arxiv/2606.25118/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.25118/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'