Discrepancy for Random Linear Codes

Computer Science > Information Theory [Submitted on 23 Jun 2026] Discrepancy for Random Linear Codes Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro 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-\frac1n\log_q |B_\rho|+\epsilon, where B_\rho is a radius-\rho Hamming ball, then with high probability |C\cap B|=(1\pm o(1))\frac{|C||B|}{q^n} simultaneously for all radius-\rho Hamming balls B\subseteq\mathbb F_q^n. This extends the classical result that such codes have covering radius at most \rho 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+\epsilon 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. Subjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Combinatorics (math.CO) Cite as: arXiv:2606.24471 [cs.IT]   (or arXiv:2606.24471v1 [cs.IT] for this version)   https://doi.org/10.48550/arXiv.2606.24471 Focus to learn more Submission history From: Jonathan Mosheiff [view email] [v1] Tue, 23 Jun 2026 12:01:54 UTC (53 KB) Access Paper: HTML (experimental) view license Current browse context: cs.IT < prev   |   next > new | recent | 2026-06 Change to browse by: cs cs.CC cs.CR math math.CO math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)