We show that random linear codes 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 applications follow:
First, random linear codes behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, a random linear code $C\subseteq \mathbb{F}_q^n$ of rate $1 - \frac{1}{n}\log_q|B_\rho| + \varepsilon$, where $|B_\rho|$ is the volume of a radius-$\rho$ Hamming ball in $\mathbb{F}_q^n$, satisfies $|C \cap B| = (1\pm o(1)) \frac{|C|\cdot |B|}{q^n}$ simultaneously for all radius-$\rho$ Hamming balls $B$ in $\mathbb{F}_q^n$ with high probability.
This significantly strengthens the best prior results, which follow from work by Blinovsky (1987, 1990) and Levitin (1988) on the covering properties of random linear codes.
Second, over prime fields, random linear codes behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime $q>2$ and input list size $2\leq \ell\leq q-1$, a random linear code $C\subseteq \mathbb{F}_q^n$ of rate $1-\log_q \ell+\varepsilon$ will satisfy $|C \cap S| = (1\pm o(1)) \frac{|C|\cdot \ell^n}{q^n}$ simultaneously for all combinatorial rectangles $S=S_1\times S_2\times\cdots\times S_n$, where $|S_i|=\ell$ for all $i$, with high probability. An analogous result also holds when we can bound $|S_i|$ only for some of the $i$'s.
In particular, we use this to show the abundance of locally leakage-resilient $n$-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap $O(n/\log n)$ over fields $\mathbb{F}_q$ of polynomial size $q=\Theta(n^\gamma)$ for a constant $\gamma\in(0,1/5)$. Prior work on the existence of leakage-resilient linear secret sharing was stuck at reconstruction thresholds above $n/2$ for both threshold and ramp schemes.
The translate-family result, and hence the list-decoding application, applies over arbitrary finite fields, even when the field size grows with $n$. The list-recovery and leakage applications over prime fields hold under moderate-growth conditions on $q$, for example $q\le n^{1/5-o(1)}$. Our results are obtained through a careful second-moment analysis of the evolution of intersection sizes as random generators are added to $C$ one by one.
Updated discussion of related work
We show that random linear codes 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 applications follow:
First, random linear codes behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, a random linear code $C\subseteq \mathbb{F}_q^n$ of rate $1 - \frac{1}{n}\log_q|B_\rho| + \varepsilon$, where $|B_\rho|$ is the volume of a radius-$\rho$ Hamming ball in $\mathbb{F}_q^n$, satisfies $|C \cap B| = (1\pm o(1)) \frac{|C|\cdot |B|}{q^n}$ simultaneously for all radius-$\rho$ Hamming balls $B$ in $\mathbb{F}_q^n$ with high probability.
This vastly generalizes the previously best known fact that random linear codes of this rate have covering radius at most $\rho n$ with high probability (Blinovsky, 1987).
Second, over prime fields, random linear codes behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime $q>2$ and input list size $2\leq \ell\leq q-1$, a random linear code $C\subseteq \mathbb{F}_q^n$ of rate $1-\log_q \ell+\varepsilon$ will satisfy $|C \cap S| = (1\pm o(1)) \frac{|C|\cdot \ell^n}{q^n}$ simultaneously for all combinatorial rectangles $S=S_1\times S_2\times\cdots\times S_n$, where $|S_i|=\ell$ for all $i$, with high probability. An analogous result also holds when we can bound $|S_i|$ only for some of the $i$'s.
In particular, we use this to show the abundance of locally leakage-resilient $n$-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap $O(n/\log n)$ over fields $\mathbb{F}_q$ of polynomial size $q=\Theta(n^\gamma)$ for a constant $\gamma\in(0,1/5)$. Prior work on the existence of leakage-resilient linear secret sharing was stuck at reconstruction thresholds above $n/2$ for both threshold and ramp schemes.
The translate-family result, and hence the list-decoding application, applies over arbitrary finite fields, even when the field size grows with $n$. The list-recovery and leakage applications over prime fields hold under moderate-growth conditions on $q$, for example $q\le n^{1/5-o(1)}$. Our results are obtained through a careful second-moment analysis of the evolution of intersection sizes as random generators are added to $C$ one by one.