Discrepancy for Random Linear Codes (opens in new tab)

We 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 rando...