Discrepancy for Random Linear Codes
Abstract
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⊆ 𝔽qn of rate 1 − 1/nlogq|Bρ| + ε, where |Bρ| is the volume of a radius-ρ Hamming ball in 𝔽qn, satisfies |C ∩ B| = (1± o(1)) (|C|· |B|)/qn simultaneously for all radius-ρ Hamming balls B with high probability. This vastly generalizes the previously best known fact that RLCs of this rate have covering radius at most ρn with high probability (Blinovsky, 1987). Second, over prime fields, RLCs 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≤ ℓ≤ q−1, an RLC C⊆ 𝔽qn of rate 1−logq ℓ+ε will satisfy |C ∩ S| = (1± o(1)) (|C|· ℓn)/qn simultaneously for all combinatorial rectangles S=S1× S2×⋯× Sn, where |Si|=ℓ for all i, with high probability. An analogous result also holds when we can bound |Si| only for some of the i's. 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 of polynomial size q=Θ(nγ) for a constant γ∈(0,1/5). Prior work was stuck at reconstruction thresholds above n/2 for both threshold and ramp schemes.
Related
- A Matroidal Framework for Random Access in Linear Codes
- Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
- Average-Radius List-Decodability of Random Linear Codes
- The list size of random linear and LDPC codes at capacity
- List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
BibTeX
@misc{doron2026discrepancy,
title = {{Discrepancy for Random Linear Codes}},
author = {Dean Doron and Tal Leonov and Jonathan Mosheiff and Henrique Navas and Nicolas Resch and João Ribeiro},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.24471},
eprint = {2606.24471},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.24471},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Discrepancy for Random Linear Codes
AU - Dean Doron
AU - Tal Leonov
AU - Jonathan Mosheiff
AU - Henrique Navas
AU - Nicolas Resch
AU - João Ribeiro
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2606.24471
UR - https://arxiv.org/abs/2606.24471
AB - 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⊆ 𝔽_q^n of rate 1 − 1/nlog_q|B_ρ| + ε, where |B_ρ| is the volume of a radius-ρ Hamming ball in 𝔽_q^n, satisfies |C ∩ B| = (1± o(1)) (|C|· |B|)/q^n simultaneously for all radius-ρ Hamming balls B with high probability. This vastly generalizes the previously best known fact that RLCs of this rate have covering radius at most ρn with high probability (Blinovsky, 1987). Second, over prime fields, RLCs 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≤ ℓ≤ q−1, an RLC C⊆ 𝔽_q^n of rate 1−log_q ℓ+ε will satisfy |C ∩ S| = (1± o(1)) (|C|· ℓ^n)/q^n simultaneously for all combinatorial rectangles S=S_1× S_2×⋯× S_n, where |S_i|=ℓ for all i, with high probability. An analogous result also holds when we can bound |S_i| only for some of the i's. 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 of polynomial size q=Θ(n^γ) for a constant γ∈(0,1/5). Prior work was stuck at reconstruction thresholds above n/2 for both threshold and ramp schemes.
ER -