{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifxt7d2b7eenluoppkuz34onkrizx6znxn6ltlvtqpabre3m3nkky",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnwgvxyqzjq2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.10399v1",
  "publishedAt": "2026-06-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Daniel Gibney",
    "Jackson Huffstutler"
  ],
  "textContent": "**Authors:** Daniel Gibney, Jackson Huffstutler\n\nMinimum-weight decoding for two-dimensional color codes is NP-hard (Walters and Turner 2026), motivating the search for approximation guarantees beyond worst-case exact decoding. We study a block-based decoder for triangular color-code lattices. The decoder satisfies the deterministic additive guarantee \\\\(\\lvert E_{\\mathrm{alg}}\\rvert \\leq \\operatorname{OPT}(S)+O(n/τ)\\\\), where \\\\(n\\\\) is the number of vertices and \\\\(τ\\\\) is the wall spacing. We show that this additive guarantee becomes a near-optimal multiplicative guarantee under natural noise models. For constant-rate i.i.d. face noise and constant local degree, choosing \\\\(τ=Θ(ε^{-1})\\\\) gives a \\\\((1+ε)\\\\)-approximation with probability \\\\(1-\\exp(-Ω(n))\\\\), in time \\\\(n2^{O(ε^{-1})}\\\\). We also prove a smoothed analogue: the same near-optimality guarantee holds when an arbitrary adversarial error pattern is perturbed by independent constant-rate noise. Finally, in the low-probability regime \\\\(p=o(1/\\log^2 n)\\\\), the syndrome decomposes into small active regions with high probability, allowing independent component-wise decoding and yielding an exact minimum-weight correction in time \\\\(n2^{O((\\log n)^{3/2})}\\\\). These results show that, despite worst-case hardness, color-code decoding admits strong average-case, smoothed, and sparse-regime guarantees.",
  "title": "Average-Case and Smoothed Near-Optimality for Color-Code Decoding"
}