Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR26-222 | 2nd November 2026 14:24

Discrepancy for Random Linear Codes

RSS-Feed




Revision #1
Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, Joao Ribeiro
Accepted on: 2nd November 2026 14:24
Downloads: 60
Keywords: 


Abstract:

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.



Changes to previous version:

Updated discussion of related work


Paper:

TR26-222 | 30th September 2026 11:38

Discrepancy for Random Linear Codes





TR26-222
Authors: Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, Joao Ribeiro
Publication: 30th September 2026 13:25
Downloads: 540
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint