{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiftur5k2k5xycw7d2ol6saqqtolp6kacpe62mt6kfppob6zpilayq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mlnly42u4pv2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.10056v1",
  "publishedAt": "2026-05-12T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Divesh Aggarwal",
    "Rishav Gupta",
    "Li Zeyong"
  ],
  "textContent": "**Authors:** Divesh Aggarwal, Rishav Gupta, Li Zeyong\n\nWe prove new hardness amplification results for Learning Parity with Noise ($\\mathsf{LPN}$) and its sparse variants. In $\\mathsf{LPN}_{η,n,m}$, the goal is to recover a secret $\\vec s\\in\\mathbb{F}_2^n$ from $m$ noisy linear samples $(\\vec a,b)$, where $\\vec a\\leftarrow \\mathbb{F}_2^n$ is uniform and $b=\\langle \\vec a,\\vec s\\rangle + e$ with $e\\leftarrow \\mathrm{Ber}(η)$. Building on the direct-product framework introduced by Hirahara and Shimizu [HS23], we show an 'instance-fraction amplification' theorem: for any $\\varepsilon,δ>0$, any algorithm that solves $\\mathsf{LPN}_{η,n,m}$ with success probability $\\varepsilon$ can be transformed into an algorithm that succeeds with probability $1-δ$ on a related \\textsf{LPN} distribution with scaled parameters $\\mathsf{LPN}_{η/k,\\;n/k,\\;m}$, where $ k=Θ\\\\!\\left(\\frac{1}δ\\log\\frac{1}{\\varepsilon}\\right). $ Equivalently, an algorithm that solves $\\mathsf{LPN}$ on a 'small fraction of instances' can be converted into an algorithm that solves $\\mathsf{LPN}$ on 'almost all instances', yielding a self-amplification for a wide range of parameters. We extend the same amplification approach to $\\mathsf{LPN}$ over $\\mathbb{F}_q$ and to Sparse-$\\mathsf{LPN}$, where each query vector $\\vec a$ has exactly $σ$ nonzero entries. Together, these results establish hardness self-amplification for a broad family of $\\mathsf{LPN}$-type problems, strengthening the foundations for assuming the average-case hardness of $\\mathsf{LPN}$ and its sparse variants.",
  "title": "Hardness Amplification for (Sparse) LPN"
}