{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiapw7wue6pnigiziwykhyczkgljynxg3xv3dexgygqnoz7aybtevy",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mozizxy7zta2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.24471v1",
  "publishedAt": "2026-06-24T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Dean Doron",
    "Tal Leonov",
    "Jonathan Mosheiff",
    "Henrique Navas",
    "Nicolas Resch",
    "João Ribeiro"
  ],
  "textContent": "**Authors:** Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro\n\nWe prove that random linear codes have nearly optimal discrepancy properties in a broad range of regimes. Our main results are two general theorems: one controlling all translates of a fixed test, and another controlling large families of Fourier-pseudorandom tests. Two motivating applications follow. First, random linear codes match unstructured random codes for list-decoding from errors above capacity. If $C\\subseteq\\mathbb F_q^n$ is a random linear code of rate $1-\\frac1n\\log_q |B_ρ|+ε$, where $B_ρ$ is a radius-$ρ$ Hamming ball, then with high probability $$ |C\\cap B|=(1\\pm o(1))\\frac{|C||B|}{q^n} $$ simultaneously for all radius-$ρ$ Hamming balls $B\\subseteq\\mathbb F_q^n$. This extends the classical result that such codes have covering radius at most $ρn$ whp (Blinovsky, 1987). Second, over prime fields, random linear codes match unstructured random codes for zero-error list-recovery above capacity. For prime $q>2$ and $2\\le \\ell\\le q-1$, a random linear code of rate $1-\\log_q\\ell+ε$ satisfies, with high probability, $$ |C\\cap S|=(1\\pm o(1))\\frac{|C|\\ell^n}{q^n} $$ simultaneously for all rectangles $S=S_1\\times\\cdots\\times S_n$ with $|S_i|=\\ell$. As a consequence, there are abundant $n$-party linear ramp secret sharing schemes over $\\mathbb F_q$ with privacy threshold about $n/(2\\log q)$ and reconstruction threshold about $5n/(2\\log q)$, resilient to balanced local leakage; prior existence results required thresholds above $n/2$ even in this case. The translate result, hence the list-decoding application, holds over arbitrary finite fields, even growing with $n$. The list-recovery and leakage applications hold over prime fields under moderate growth, e.g. $q\\le n^{1/5-o(1)}$. The proofs use a refined second-moment analysis tracking intersection sizes as random generators are added to $C$.",
  "title": "Discrepancy for Random Linear Codes"
}