{"id":"arxiv/2606.24471","url":"https://arxiv.org/abs/2606.24471","tags":["cs.IT","cs.CC","cs.CR","math.CO"],"score":0,"title":"Discrepancy for Random Linear Codes","domain":"cs.IT","source":"arxiv","authors":["Dean Doron","Tal Leonov","Jonathan Mosheiff","Henrique Navas","Nicolas Resch","João Ribeiro"],"reviews":0,"subject":"cs.IT","summary":"We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating examples follow: First, RLCs behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, an RLC $C\\subseteq \\mathbb{F}_q^n$ of rate $1 - \\frac{1}{n}\\log_q|B_ρ| + \\varepsilon$, where $|B_ρ|$ is the volume of a radius-$ρ$ Hamming ball in…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-23","reactions":{}}