Discrepancy for Random Linear Codes

Abstract

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 random linear code of rate $1-\frac{1}{n}{\log }_q|B_{\ddot{I}}|+\hat{I}\mu$, where $B_{\ddot{I}}$ is a radius-$\ddot{I}$ Hamming ball, then with high probability $$|C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n}$$ simultaneously for all radius-$\ddot{I}$ Hamming balls $B\subseteq {\mathbb{F}}_q^n$. This extends the classical result that such codes have covering radius at most $\ddot{I}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 +\hat{I}\mu$ 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$.