{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigierlegqhefshz5l77vjp7cpkdckhzp7qxwl466f7zeb2e5tptym",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmnyqb4rujs2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.23517v1",
  "publishedAt": "2026-05-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jack Stade"
  ],
  "textContent": "**Authors:** Jack Stade\n\nWe prove a PCP theorem for the existential theory of the reals, showing that MAX-ETR-INV is $\\exists\\mathbb{R}$-hard to approximate to within some constant factor. The existential theory of the reals (ETR) is a decision problem asking if there exists a set of real-valued variables satisfying some constraints involving polynomials and inequalities, and $\\exists\\mathbb{R}$ is the complexity class of problems polynomial-time reducible to ETR. Many important geometric problems are known to be $\\exists\\mathbb{R}$-complete. $\\exists\\mathbb{R}$-hardness results frequently work by a reduction from the $\\exists\\mathbb{R}$-complete problem ETR-INV, which asks if there is a an assignment of real variables each in the interval $[\\frac12, 2]$ satisfying some constraints of form $x=1$, $xy=1$ and $x+y=z$. MAX-ETR-INV is a related optimization problem that asks, given a set of constraints of form $x=1$, $xy=1$, and $x+y=z$, for a feasible (that is, satisfiable with variables in $[\\frac12, 2]$) subset of those constraints of the largest possible size. We show that there is some constant $ε>0$ such that it is $\\exists\\mathbb{R}$-hard to approximate MAX-ETR-INV better than a $1-ε$ factor. This means that even a non-deterministic polynomial-time algorithm can't approximate MAX-ETR-INV better than this factor unless $\\exists\\mathbb{R}=\\text{NP}$. We also give a polynomial-time $8$-factor approximation algorithm and a non-deterministic-polynomial-time $2$-factor approximation algorithm for MAX-ETR-INV.",
  "title": "Probabilistically checkable proofs for the Existential Theory of the Reals"
}