{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifg7poufqliqeuedb7zvz7rm3hht5qqjfti67lxn6i7c4j3vxuy2y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mp3ewo2toel2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.25118v1",
  "publishedAt": "2026-06-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Nikolas Gärtner",
    "Victor Magron",
    "Frank Vallentin"
  ],
  "textContent": "**Authors:** Nikolas Gärtner, Victor Magron, Frank Vallentin\n\nIn 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.",
  "title": "Sums of squares in polynomial time"
}