{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigwpe6giagy4xsm63i77vyxkhpubon4wje6hc3c3ap6oysclohf2i",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mg7empmvuhd2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.03219v1",
  "publishedAt": "2026-03-04T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Huck Bennett",
    "Peter Ly"
  ],
  "textContent": "**Authors:** Huck Bennett, Peter Ly\n\nWe study the hardness of the $γ$-approximate decisional Covering Radius Problem on lattices in the $\\ell_p$ norm ($γ$-$\\text{GapCRP}_p$). Specifically, we prove that there is an explicit function $γ(p)$, with $γ(p) > 1$ for $p > p_0 \\approx 35.31$ and $\\lim_{p \\to \\infty} γ(p) = 9/8$, such that for any constant $\\varepsilon > 0$, $(γ(p) - \\varepsilon)$-$\\text{GapCRP}_p$ is $\\mathsf{NP}$-hard. This shows the first hardness of $\\text{GapCRP}_p$ for explicit $p < \\infty$. Work of Haviv and Regev (CCC, 2006 and CJTCS, 2012) previously showed $Π_2$-hardness of approximation for $\\text{GapCRP}_p$ for all sufficiently large (but non-explicit) finite $p$ and for $p = \\infty$. In fact, our hardness results hold for a variant of $\\text{GapCRP}$ called the Binary Covering Radius Problem ($\\text{BinGapCRP}$), which trivially reduces to both $\\text{GapCRP}$ and the decisional Linear Discrepancy Problem ($\\text{LinDisc}$) in any norm in an approximation-preserving way. We also show $Π_2$-hardness of $(9/8 - \\varepsilon)$-$\\text{BinGapCRP}$ in the $\\ell_{\\infty}$ norm for any constant $\\varepsilon > 0$. Our work extends and heavily uses the work of Manurangsi (IPL, 2021), which showed $Π_2$-hardness of $(9/8 - \\varepsilon)$-$\\text{LinDisc}$ in the $\\ell_{\\infty}$ norm.",
  "title": "Hardness of the Binary Covering Radius Problem in Large $\\ell_p$ Norms"
}