{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibn7q4mohuruefsachzlbqw2u4fhoowzcp6r4rz25fvublziamoea",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjlo7qsekk72"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.13971v1",
  "publishedAt": "2026-04-16T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Hsien-Chih Chang",
    "Suprovat Ghoshal",
    "Euiwoong Lee"
  ],
  "textContent": "**Authors:** Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee\n\nWe study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $α_{GW}\\approx 0.87856$, it is natural to ask whether one can beat $α_{GW}$ when the SDP solution lives in $\\mathbb{R}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(α_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections.",
  "title": "Max Cut with Small-Dimensional SDP Solutions"
}