{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigbmuag5pnr2wvw2uwg4lx2v6f2fapuz7fz2xbn6nloxlvry5xqie",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjivzegbrzn2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.10457v1",
  "publishedAt": "2026-04-14T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Songtao Mao"
  ],
  "textContent": "**Authors:** Songtao Mao\n\nNoisy $k$-XOR is a basic average-case inference problem in which one observes random noisy $k$-ary parity constraints and seeks to recover, or more weakly, detect, a hidden Boolean assignment. A central question is to characterize the tradeoff among sample complexity, noise level, and running time. We give a recovery algorithm, and hence also a detection algorithm, for noisy $k$-XOR in the high-noise regime. For every parameter $D$, our algorithm runs in time $n^{D+O(1)}$ and succeeds whenever $$ m \\ge C_k \\frac{n^{k/2}}{D^{\\,k/2-1}δ^2}, $$ where $C_k$ is an explicit constant depending only on $k$, and $δ$ is the noise bias. Our result matches the best previously known time--sample tradeoff for detection, while simultaneously yielding recovery guarantees. In addition, the dependence on the noise bias $δ$ is optimal up to constant factors, matching the information-theoretic scaling. We also prove matching low-degree lower bounds. In particular, we show that the degree-$D$ low-degree likelihood ratio has bounded $L^2$-norm below the same threshold, up to the same factor $D^{k/2-1}$. Under the low-degree heuristic, this implies that our algorithm is near-optimal over a broad range of parameters. Our approach combines a refined second-moment analysis with color coding and dynamic programming for structured hypergraph embedding statistics. These techniques may be of independent interest for other average-case inference problems.",
  "title": "Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic"
}