pith. sign in

arxiv: 2606.24471 · v1 · pith:OAB7EZWNnew · submitted 2026-06-23 · 💻 cs.IT · cs.CC· cs.CR· math.CO· math.IT

Discrepancy for Random Linear Codes

Dean Doron , Tal Leonov , Jonathan Mosheiff , Henrique Navas , Nicolas Resch , Jo\~ao Ribeiro This is my paper

Pith reviewed 2026-06-25 22:55 UTC · model grok-4.3

classification 💻 cs.IT cs.CCcs.CRmath.COmath.IT
keywords random linear codesdiscrepancylist decodingHamming ballsrectanglessecret sharing
0
0 comments X

The pith

Random linear codes intersect every radius-ρ Hamming ball in proportion (1±o(1))|C||B|/q^n with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that random linear codes achieve nearly the same uniform intersection properties with structured test sets as fully random codes. For a code of rate 1-(1/n)log_q|B_ρ|+ε, the size of the intersection with any Hamming ball of radius ρ is asymptotically the expected value, simultaneously over all such balls. An analogous uniform statement holds for all rectangles of a fixed side length ℓ over prime fields when the rate is 1-log_q ℓ+ε. These properties follow from a refined second-moment calculation that monitors how intersections evolve while random generators are added one by one. The results directly imply that random linear codes match the list-decoding and list-recovery performance of unstructured random codes above capacity.

Core claim

A random linear code C⊆F_q^n of rate 1-(1/n)log_q|B_ρ|+ε satisfies |C∩B|=(1±o(1))|C||B|/q^n simultaneously for all radius-ρ Hamming balls B, with high probability. Over prime fields q>2, a random linear code of rate 1-log_q ℓ+ε satisfies |C∩S|=(1±o(1))|C|ℓ^n/q^n simultaneously for all rectangles S=S_1×⋯×S_n with |S_i|=ℓ. Both statements hold with high probability and extend classical covering-radius results.

What carries the argument

refined second-moment analysis tracking intersection sizes with the test sets as random generators are added successively to build the linear code

Load-bearing premise

The second-moment analysis on intersection sizes remains concentrated after conditioning on the linear dependencies among the generators and after taking union bounds over all balls or rectangles.

What would settle it

An explicit variance calculation or moderate-size simulation exhibiting a random linear code whose intersection with some Hamming ball deviates by more than o(1) times the mean.

read the original 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-\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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that random linear codes achieve nearly optimal discrepancy: for rate 1 - (1/n) log_q |B_ρ| + ε, |C ∩ B| = (1 ± o(1)) |C| |B| / q^n holds simultaneously for all radius-ρ Hamming balls B (over arbitrary fields); a parallel uniform intersection statement holds for all ℓ-rectangles over prime fields q ≤ n^{1/5-o(1)}. The proofs rely on a refined second-moment analysis that tracks intersection sizes while successively adding random generators to the code.

Significance. If the variance control in the second-moment analysis holds, the results extend Blinovsky's covering-radius theorem to full discrepancy and yield the first linear-code constructions for zero-error list-recovery above capacity, plus improved ramp secret-sharing schemes with privacy/reconstruction thresholds n/(2 log q) and 5n/(2 log q) that tolerate balanced local leakage. The parameter-free nature of the main claims and the explicit field-growth restrictions are strengths.

major comments (2)
  1. [Proofs of the two main theorems (refined second-moment analysis)] The refined second-moment analysis must produce Var[|C ∩ T|] = o(E[|C ∩ T|]^2) uniformly over the test family after conditioning on linear independence of the generators; the abstract invokes this without an explicit variance expression or error-term regime, which is load-bearing for the union bound over exponentially many balls/rectangles when q grows.
  2. [Rectangle theorem and list-recovery application] For the rectangle result the restriction q ≤ n^{1/5-o(1)} appears to arise from a poly(q) factor inside the variance bound; it is unclear whether this is an artifact of the analysis or fundamental, and whether the o(1) term absorbs the log(#tests) factor from the union bound for the stated range.
minor comments (2)
  1. The citation “Blinovsky, 1987” should be expanded to a full bibliographic entry.
  2. The notion of “Fourier-pseudorandom tests” used in the second general theorem should be defined explicitly before the statement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below, agreeing to incorporate clarifications on the variance analysis and parameter restrictions.

read point-by-point responses

  1. Referee: [Proofs of the two main theorems (refined second-moment analysis)] The refined second-moment analysis must produce Var[|C ∩ T|] = o(E[|C ∩ T|]^2) uniformly over the test family after conditioning on linear independence of the generators; the abstract invokes this without an explicit variance expression or error-term regime, which is load-bearing for the union bound over exponentially many balls/rectangles when q grows.

    Authors: We agree that the abstract would benefit from an explicit reference to the variance control. Sections 3 and 4 derive that, after conditioning on linear independence of the generators, Var[|C ∩ T|] = o(E[|C ∩ T|]^2) holds uniformly over the relevant test families, with explicit error terms polynomial in the parameters that suffice for the union bound. The o(1) deviation absorbs the logarithmic factors from the number of tests. We will revise the abstract and introduction to summarize this variance regime and error-term dependence. revision: yes

  2. Referee: [Rectangle theorem and list-recovery application] For the rectangle result the restriction q ≤ n^{1/5-o(1)} appears to arise from a poly(q) factor inside the variance bound; it is unclear whether this is an artifact of the analysis or fundamental, and whether the o(1) term absorbs the log(#tests) factor from the union bound for the stated range.

    Authors: The restriction q ≤ n^{1/5-o(1)} arises from a poly(q) factor in the variance bound for rectangles (Lemma 5.3). This appears to be an artifact of the current Fourier-analytic second-moment method rather than fundamental, as the translate theorem has no field-size restriction. The o(1) term is chosen to absorb the union-bound factor log(#tests) ≈ n log q, which holds in the stated range. We will add a clarifying paragraph in Section 5 discussing the origin of the restriction and confirming the union bound is controlled. revision: yes

Circularity Check

0 steps flagged

No circularity; direct second-moment analysis on random linear codes

full rationale

The derivation consists of a standard probabilistic argument using refined second-moment method to track intersection sizes while adding random generators to form the linear code C. This is grounded in external combinatorial facts about Hamming balls and rectangles, with an explicit external citation to Blinovsky 1987 for the covering-radius case. No parameters are fitted to data and then relabeled as predictions, no self-citations are load-bearing for the central claim, and the result does not reduce to its inputs by definition or renaming. The argument is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard probabilistic method and second-moment calculations over finite fields. No free parameters are fitted to data; the only parameters are the rate offset ε and the field-size growth conditions stated in the abstract.

axioms (2)
  • standard math Standard second-moment method applies to the indicator variables for codeword membership in each test set after linear generators are added sequentially.
    Invoked in the proof sketch for both main theorems.
  • domain assumption Union bound over all Hamming balls (or all rectangles) succeeds when the per-test deviation probability is sufficiently small.
    Required for the simultaneous statement over all tests.

pith-pipeline@v0.9.1-grok · 5963 in / 1451 out tokens · 12389 ms · 2026-06-25T22:55:40.247998+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 2 linked inside Pith

  1. [1]

    Linear hash functions

    Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and G \'a bor Tardos. Linear hash functions. Journal of the ACM (JACM) , 46(5):667--683, 1999

    1999

  2. [2]

    Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields

    Omar Alrabiah, Venkatesan Guruswami, and Ray Li. Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1458--1469, 2024

    2024

  3. [3]

    Handbook of mathematical functions with formulas, graphs, and mathematical tables , volume 55

    Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables , volume 55. US Government printing office, 1948

    1948

  4. [4]

    Combinatorial bounds for list recovery via discrete Brascamp-Lieb inequalities

    Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang. Combinatorial bounds for list recovery via discrete Brascamp-Lieb inequalities. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 365--376, 2026

    2026

  5. [5]

    On the local leakage resilience of linear secret sharing schemes

    Fabrice Benhamouda, Akshay Degwekar, Yuval Ishai, and Tal Rabin. On the local leakage resilience of linear secret sharing schemes. Journal of Cryptology , 34(2), February 2021. Preliminary version in CRYPTO 2018

    2021

  6. [6]

    Generic Reed-Solomon codes achieve list-decoding capacity

    Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. Generic Reed-Solomon codes achieve list-decoding capacity. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1488--1501, 2023

    2023

  7. [7]

    Lower asymptotic bound on the number of linear code words in a sphere of given radius in F _q^n

    Vladimir Markovich Blinovskii. Lower asymptotic bound on the number of linear code words in a sphere of given radius in F _q^n . Problemy Peredachi Informatsii , 23(2):50--53, 1987. Translated in: Problems of Information Transmission, vol. 23, no. 2, pp. 130--132

    1987

  8. [8]

    A note on second-order expected maximum-load bounds for binary linear hashing

    Nader H Bshouty. A note on second-order expected maximum-load bounds for binary linear hashing. arXiv preprint arXiv:2605.18335 , 2026

    Pith/arXiv arXiv 2026

  9. [9]

    Bounds on the threshold gap in secret sharing and its applications

    Ignacio Cascudo, Ronald Cramer, and Chaoping Xing. Bounds on the threshold gap in secret sharing and its applications. IEEE Transactions on Information Theory , 59(9):5600--5612, 2013

    2013

  10. [10]

    Restricted isometry of Fourier matrices and list decodability of random linear codes

    Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SIAM Journal on Computing , 42(5):1888--1914, 2013

    1914

  11. [11]

    OPI soft decoders

    Andr \'e Chailloux. OPI soft decoders. arXiv preprint arXiv:2511.22691 , 2025

    arXiv 2025

  12. [12]

    Covering Codes , volume 54 of North-Holland Mathematical Library

    G \'e rard Cohen, Iiro Honkala, Simon Litsyn, and Antoine Lobstein. Covering Codes , volume 54 of North-Holland Mathematical Library . Elsevier, 1997

    1997

  13. [13]

    Quantum advantage from soft decoders

    Andr \'e Chailloux and Jean-Pierre Tillich. Quantum advantage from soft decoders. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 738--749, 2025

    2025

  14. [14]

    Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized Singleton bounds

    Yeyuan Chen and Zihan Zhang. Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized Singleton bounds. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1–12, New York, NY, USA, 2025. Association for Computing Machinery

    2025

  15. [15]

    Linear hashing with _ guarantees and two-sided Kakeya bounds

    Manik Dhar and Zeev Dvir. Linear hashing with _ guarantees and two-sided Kakeya bounds. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 419--428. IEEE, 2022

    2022

  16. [16]

    List-recovery of random linear codes over small fields

    Dean Doron, Jonathan Mosheiff, Nicolas Resch, and Jo \ a o Ribeiro. List-recovery of random linear codes over small fields. IEEE Transactions on Information Theory , 2025

    2025

  17. [17]

    On the list-decodability of random linear codes

    Venkatesan Guruswami, Johan H stad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Transactions on Information Theory , 57(2):718--725, 2011

    2011

  18. [18]

    Combinatorial bounds for list decoding

    Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory , 48(5):1021--1034, 2002

    2002

  19. [19]

    Bounds for list-decoding and list-recovery of random linear codes

    Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. IEEE Transactions on Information Theory , 68(2):923--939, 2021

    2021

  20. [20]

    Essential Coding Theory

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential Coding Theory . 2025. Draft available at https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf

    2025

  21. [21]

    List decoding from erasures: bounds and code constructions

    Venkatesan Guruswami. List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory , 49(11):2826--2833, 2003

    2003

  22. [22]

    Randomly punctured Reed-Solomon codes achieve the list decoding capacity over polynomial-size alphabets

    Zeyu Guo and Zihan Zhang. Randomly punctured Reed-Solomon codes achieve the list decoding capacity over polynomial-size alphabets. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 164--176. IEEE, 2023

    2023

  23. [23]

    Linear hashing is optimal

    Michael Jaber, Vinayak M Kumar, and David Zuckerman. Linear hashing is optimal. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 245--255, 2025

    2025

  24. [24]

    Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V

    Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush. Optimization by decoded quantum interferometry. Nature , 646(8086):831--836, 2025

    2025

  25. [25]

    An improvement upon the bounds for the local leakage resilience of Shamir’s secret sharing scheme

    Dustin Kasser. An improvement upon the bounds for the local leakage resilience of Shamir’s secret sharing scheme. In Theory of Cryptography Conference (TCC) , page 395–422. Springer Nature Switzerland, December 2024

    2024

  26. [26]

    New bounds on the local leakage resilience of Shamir’s secret sharing scheme

    Ohad Klein and Ilan Komargodski. New bounds on the local leakage resilience of Shamir’s secret sharing scheme. In Advances in Cryptology – CRYPTO 2023 , page 139–170. Springer Nature Switzerland, 2023

    2023

  27. [27]

    Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, and Stephen P. Jordan. Verifiable quantum advantage via optimized dqi circuits. arXiv preprint arXiv:2510.10967 , 2025

    arXiv 2025

  28. [28]

    Random Reed-Solomon codes and random linear codes are locally equivalent

    Matan Levi, Jonathan Mosheiff, and Nikhil Shagrithaya. Random Reed-Solomon codes and random linear codes are locally equivalent. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2097--2131. IEEE, 2025

    2025

  29. [29]

    On the basic averaging arguments for linear codes

    Hans-Andrea Loeliger. On the basic averaging arguments for linear codes. In Communications and Cryptography: Two Sides of One Tapestry , pages 251--261. Springer, 1994

    1994

  30. [30]

    Near-optimal list-recovery of linear code families

    Ray Li and Nikhil Shagrithaya. Near-optimal list-recovery of linear code families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , pages 53--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2025

    2025

  31. [31]

    Improved list-decodability of random linear binary codes

    Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes. IEEE Transactions on Information Theory , 67(3):1522--1536, 2020

    2020

  32. [32]

    Some applications of coding theory in cryptography

    James L Massey. Some applications of coding theory in cryptography. Codes and Ciphers: Cryptography and Coding IV , pages 33--47, 1995

    1995

  33. [33]

    Maji, Anat Paskin-Cherniavsky , Tom Suad, and Mingyuan Wang

    Hemanta K. Maji, Anat Paskin-Cherniavsky , Tom Suad, and Mingyuan Wang. Constructing locally leakage-resilient linear secret-sharing schemes. In Advances in Cryptology – CRYPTO 2021 , page 779–808. Springer International Publishing, 2021

    2021

  34. [34]

    Hai H. Nguyen. Towards breaking the half-barrier of local leakage-resilient Shamir's secret sharing. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology -- CRYPTO 2024 , pages 257--285, Cham, 2024. Springer Nature Switzerland

    2024

  35. [35]

    A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem

    Ansis Rosmanis. A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem. arXiv preprint arXiv:2601.15171 , 2026

    arXiv 2026

  36. [36]

    Every list-decodable code for high noise has abundant near-optimal rate puncturings

    Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 764--773, 2014

    2014

  37. [37]

    Average-radius list-recoverability of random linear codes

    Atri Rudra and Mary Wootters. Average-radius list-recoverability of random linear codes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 644--662. SIAM, 2018

    2018

  38. [38]

    Threshold rates of code ensembles: Linear is best

    Nicolas Resch and Chen Yuan. Threshold rates of code ensembles: Linear is best. IEEE Transactions on Information Theory , 70(7):4823--4842, 2024

    2024

  39. [39]

    Generalized Singleton bound and list-decoding Reed--Solomon codes beyond the Johnson radius

    Chong Shangguan and Itzhak Tamo. Generalized Singleton bound and list-decoding Reed--Solomon codes beyond the Johnson radius. SIAM Journal on Computing , 52(3):684--717, 2023

    2023

  40. [40]

    On worst-case optimal polynomial intersection

    Yihang Sun and Mary Wootters. On worst-case optimal polynomial intersection. arXiv preprint arXiv:2604.09533 , 2026

    Pith/arXiv arXiv 2026

  41. [41]

    Leakage-resilient secret sharing with constant share size

    Ivan Tjuawinata and Chaoping Xing. Leakage-resilient secret sharing with constant share size. IEEE Transactions on Information Theory , 68(12):8228--8250, 2022

    2022

  42. [42]

    On the list decodability of random linear codes with large error rates

    Mary Wootters. On the list decodability of random linear codes with large error rates. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages 853--860, 2013

    2013

  43. [43]

    List concatenated decoding

    Victor Vasilievich Zyablov and Mark Semenovich Pinsker. List concatenated decoding. Problemy Peredachi Informatsii , 17(4):29--33, 1981

    1981