Pith. sign in

REVIEW 2 major objections 6 minor 41 references

List-Recovery of Random Linear Codes over Small Fields

T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random linear codes over constant-size fields are shown to be list-recoverable with output list size only $O(1/\varepsilon)$ when their rate is $\varepsilon$ below capacity, improving the classical exponential bound.

desk verdict First real improvement over Zyablov–Pinsker for small-alphabet list-recovery: random linear codes get O(1/ε) list size near capacity, with two fixable gaps in stated constants and the ℓ=1 erasures case. read the letter →

arxiv 2505.05935 v1 pith:RIZW3CCR submitted 2025-05-09 cs.IT math.IT

Dean Doron , Jonathan Mosheiff , Nicolas Resch , João Ribeiro This is my paper · ORCID
classification cs.ITmath.IT MSC 94B3594B0511T7160C05
keywords list-recoveryrandomlinearcodeslist-decodingerasureserrorsdelta-mixingsmall-alphabetregimeZyablov-Pinskerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that random linear codes over small fields can be list-recovered with output list size only linear in the gap to capacity, rather than exponential. For list-recovery from erasures over prime fields, a random linear code of rate $\varepsilon$ below the erasure capacity is shown to be $(\alpha,\ell,C_1/\varepsilon)$-list-recoverable; for list-recovery from errors over arbitrary prime-power fields, rate $\varepsilon$ below the error capacity gives $(\rho,\ell,C_2/\varepsilon)$-list-recoverability. The constants $C_1$ and $C_2$ depend only on the decoding radius, input list size, and alphabet size. This is the first improvement over the Zyablov–Pinsker bound $q^{O(\ell/\varepsilon)}$ in the small-alphabet regime, and it shows that in these regimes linearity does not force an exponential price in $1/\varepsilon$.

What carries the argument

The load-bearing object is the $\delta$-mixing property: for a set $T\subseteq \mathbb{F}_q^n$, two independent uniform samples $X,X'$ satisfy $\Pr[\alpha X+\beta X'\in T+z]\leq q^{-\delta n}$ for all nonzero $\alpha,\beta\in\mathbb{F}_q$ and all shifts $z\in\mathbb{F}_q^n$. This is the property that random linear subspaces cannot correlate with the sets that threaten list-recovery. The paper establishes it separately for the two relevant set families: combinatorial rectangles $T_1\times\cdots\times T_n$ over prime fields, using a centered-interval extremal bound for sums of subsets of $\mathbb{F}_q$, and list-recovery balls $B_\rho(T_1\times\cdots\times T_n)$ over arbitrary fields, using a convolution identity. An increasing-chain lemma then converts a set that is $\delta$-mixing into one that meets any random linear code of rate $\varepsilon$ below capacity in at most $C/\varepsilon$ points.

What would settle it

Take $T=\{0\}\subseteq \mathbb{F}_q$, $\alpha=\beta=1$, and $\gamma=0$. Since the two samples always equal $0$, $\Pr[\alpha X+\beta X'\in T+\gamma]=1>q^{-\delta}$ for every $\delta>0$, so $T$ is not $\delta$-mixing. Because the erasures proof's only path to list-size bounds goes through $\delta$-mixing of the rectangles $T_1\times\cdots\times T_n$, this calculation shows the proof as written does not cover $\ell=1$, and any repair must either handle $\ell=1$ separately or change the mixing definition.

Watch

Extended reading notes

Core claim

The central discovery is that the sets a list-recovery decoder must avoid---combinatorial rectangles for erasures and puffed-up list-recovery balls for errors---are $\delta$-mixing for a constant $\delta>0$, and that this mixing property directly controls the output list size. For erasures over prime fields, the worst-case size-$\ell$ subset of $\mathbb{F}_q$ is a centered interval; two independent samples from such an interval sum back into it with probability at most $3/4+O(1/\ell^2)$, giving $\delta\geq \log_q(16/13)$ for $\ell\leq 2q/3$. For errors over any field, the paper proves the coordinate-wise collision probability with a list-recovery ball satisfies $\Pr[E_i=1]\leq (1-\rho)^2+\rho^2 \ell/(q-\ell)$, which is less than $1-\rho$ exactly when $\rho<1-\ell/q$, the regime in which positive-rate list-recovery is possible. Feeding these mixing bounds into the increasing-chain argument of [GHK11] gives the list-size bound $L=C/\varepsilon$ for both models, with explicit constants.

Load-bearing premise

The erasures theorem is stated for every input list size $\ell\leq q-1$, but its proof relies on a $\delta$-mixing lemma established only for $2\leq\ell\leq q-1$; for $\ell=1$ a singleton input set is not $\delta$-mixing at all, so the stated proof does not cover the case $\ell=1$.

Editorial extensions

If this is right

  • For any fixed alphabet size $q$, input list size $\ell$, and decoding radius, the output list size is $O(1/\varepsilon)$, matching the Elias-bound dependence that plain random codes achieve.
  • The bounds improve on the Zyablov–Pinsker bound $q^{O(\ell/\varepsilon)}$ whenever $q\leq 2^{(1/\varepsilon)^c}$ for some small universal constant $c>0$, i.e., throughout the small-alphabet regime.
  • Over prime fields, the erasures result is essentially optimal in its $\varepsilon$-dependence, since a previous lower bound shows exponential list size is necessary for low-characteristic fields.
  • Over arbitrary fields, the errors result shows no price for linearity in the $\varepsilon$-dependence, in contrast to the large-alphabet regime where an exponential lower bound applies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the errors-side collision calculation never uses primality of $q$, the same $O(1/\varepsilon)$ list-size bound should extend to random linear codes over any finite field (or any group alphabet) with the same condition $\rho<1-\ell/q$.
  • The paper's coordinate-wise mixing bound is strong enough that the method plausibly yields average-radius list-recovery, a stronger guarantee the paper itself raises as a natural next step.
  • The constant $C_1$ in the erasures theorem inherits the crude $3/4$ bound for centered intervals; a tighter additive-combinatorics estimate would directly improve the explicit constants without changing the argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies list-recovery of random linear codes over small fields at rates epsilon below capacity, and proves upper bounds of the form L = O(1/epsilon) on the output list size. For list-recovery from erasures over prime fields, Theorem 3.5 claims L <= C/epsilon for every 1 <= l <= q-1, improving the Zyablov-Pinsker q^{O(l/epsilon)} bound. For list-recovery from errors over arbitrary fields, Theorem 4.7 claims a similar L <= C/epsilon bound. The technical approach adapts the Guruswami-Hastad-Kopparty mixing method: it establishes a weak 'delta-mixing' property for the relevant sets (combinatorial rectangles for erasures, list-recovery balls for errors) and then applies an increasing-chain argument to bound the intersection of a random linear code with those sets. The paper also provides explicit constants and compares its results with lower bounds for low-characteristic fields and large alphabets.

Significance. If the stated results hold, they settle the dependence of the output list size on the gap-to-capacity epsilon for two natural regimes of list-recovery, showing that random linear codes achieve the Elias-type bound L = O(1/epsilon) for constant alphabet size. This is a meaningful step beyond the classical Zyablov-Pinsker bound, and the erasures result over prime fields is a clean application of Lev's theorem on additive structure. The paper is largely self-contained, gives explicit constants, and correctly distinguishes the regimes where linearity is or is not costly. However, the proof of Theorem 3.5 does not cover the case l=1, which is explicitly included in the statement, and the proof of Corollary 4.6 claims a mixing rate that is not justified by the derived exponential bounds. Both issues are local and appear repairable, but they currently affect the validity of two central stated results.

major comments (2)
  1. [Theorem 3.5 / §3.2] Theorem 3.5 is stated for every integer 1 <= l <= q-1, but its proof relies on Corollary 3.3, which establishes delta-mixing only for subsets of size at least 2. For l=1, a singleton T={0} subset of F_q is not delta-mixing for any delta>0: with alpha=beta=1 and gamma=0, Pr[alpha X + beta X' in T+gamma] = 1, contradicting Definition 2.17. Since the proof of Theorem 3.5 sets delta >= (1-alpha) delta_0 using Corollary 3.3, it has no mechanism to handle l=1. This is load-bearing because the abstract and introduction explicitly claim the erasures result for all l, and l=1 corresponds to ordinary list-decoding from erasures. The theorem should either be restricted to l >= 2 or supplemented with a separate argument for l=1.
  2. [Corollary 4.6 / §4.1] The stated value of delta in Corollary 4.6 is not justified by the preceding inequalities. Equation (23) proves a bound of the form exp_q(-rho^4 (1-l/q-rho)^2/(16 log q) * n), with no factor of log_q((q-l)(1-rho)/(rho l)). The proof's concluding sentence inserts this log_q factor into the exponent of the final bound, effectively multiplying the decay rate from (23) by a factor that can be large when rho is small. Since the sum of the two exponential bounds decays at the minimum of the two rates, the claimed delta exceeds the true rate supplied by (23). The proof should either drop the log_q factor from delta or strengthen the bound on (21). This is load-bearing for the explicit constant in Theorem 4.7, although the asymptotic L = O(1/epsilon) claim is very likely repairable by taking the smaller delta.
minor comments (6)
  1. [Lemma 3.4 / §3.2] The hypothesis 'n >= q^{8a/delta}' does not by itself suffice for the proof step where b(A+1) <= (delta d - 1)/2 n; the proof silently requires n to be large relative to b. Since in the application b is at most L+1 and n is chosen large, this does not affect the asymptotic conclusion, but the condition should be stated precisely.
  2. [Theorem 3.5 proof] The bound on the number of input configurations replaces (e q/l)^{(1-alpha) n l} by q^{(1-alpha) n l}. This is not valid for l=2, since e q/2 > q. The error can be absorbed into the constants by increasing a and c, but the displayed inequality is false as written.
  3. [Lemma 4.4 / §4.1] There is a small notational confusion in the proof: the scalars are called alpha_1, alpha_2 but the sets are written alpha_i T_i. The intended meaning is that the first sample is scaled by alpha_1 and the second by alpha_2; the notation should be made consistent.
  4. [Section 4 intro] The opening paragraph refers to 'Theorem 3.2' when invoking the erasures argument; the intended reference is Lemma 3.4 (and Theorem 3.5). This is a harmless citation slip but should be corrected.
  5. [Theorems 3.5 and 4.7] Both theorems state simple largeness conditions on n (e.g., n >= L, or n >= (log q/(rho(1-l/q-rho)))^c), but their proofs use additional largeness conditions such as h_2(alpha)/log q + 2 log b*/n <= 1. These auxiliary conditions should be included in the theorem statements or shown to follow from the stated conditions.
  6. [Theorem 1.2 vs Theorem 3.5] The introduction states the erasures result for 1 <= l <= q, while Theorem 3.5 requires l <= q-1. For l = q the capacity is zero, so the range in the introduction appears to be a typo; it should be aligned with the theorem statement.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the list-size upper bounds follow from external mixing theorems and standard random-code arguments.

full rationale

The paper's derivation chain is self-contained given external ingredients. For erasures, the crucial mixing statement (Corollary 3.3) is derived from Lev's theorem (Lemma 3.1), an external published result, with an explicit computation in Lemma 3.2. For errors, Lemma 4.2 and Corollary 4.6 establish δ-mixing of list-recovery balls directly from convolution identities and Chernoff bounds, without invoking the target list-size bound. The translation from mixing to list recovery uses the GHK11 increasing-chain lemma (Lemma 2.16) and the standard probability that a fixed set of independent vectors lies in a random linear code (Proposition 2.1). The constants C(α,ℓ,q) and C(ρ,ℓ,q) are explicit and chosen after the proof to satisfy the required inequalities; they are not fitted parameters or renamed outputs. Self-citations ([GLM+22], [KM25], [Res20]) provide lower bounds, context, or standard ball-size estimates, and none of them is used to derive the main upper-bound theorems. The ℓ=1 gap in Theorem 3.5, noted by the reader, is a correctness gap rather than a circular step: Corollary 3.3 covers only ℓ≥2, and singleton subsets are not δ-mixing for δ>0, but this is an unproved case, not a self-justifying reduction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on published external lemmas (Lev, GHK11), standard concentration inequalities, and known capacity theorems for list-recovery. No ad hoc assumptions or fitted constants are introduced. The only non-standard concepts are the mixing definitions, which are new but proven within the paper.

assumptions (4)
  • standard math Lev's theorem on sums of subsets of F_p (Lemma 3.1) characterizes worst-case convolution probabilities via centered intervals.
    Used to prove worst-case mixing of subsets of prime fields (Lemma 3.2, Corollary 3.3). Cited from [Lev01].
  • standard math GHK11 increasing-chain lemma (Lemma 2.16) provides long increasing chains in any large subset of F_q^ℓ.
    Used in Lemma 3.4 to bound the intersection of a span with a mixing set. Cited from [GHK11].
  • standard math For a random linear code of rate R, Pr[all of v1,...,vb in code] = q^{-(1-R)n dim(Span)} (Prop 2.1).
    Basic linear algebra over random matrices; used throughout the union bounds.
  • domain assumption The capacity thresholds for list-recovery from errors and erasures (Theorems 2.4 and 2.8) and the list-recovery ball size estimate (Prop 2.6).
    Standard results from prior work [Res20]; used to set rate = capacity - ε.

how reviews work

0 comments
Cite this review

Pith. "Pith review of List-Recovery of Random Linear Codes over Small Fields." pith.science (2026). https://pith.science/paper/RIZW3CCR

@misc{pith2026250505935,
  author       = {Pith},
  title        = {Pith review of: List-Recovery of Random Linear Codes over Small Fields},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RIZW3CCR}},
  note         = {Machine review of arXiv:2505.05935}
}
abstract

We study list-recoverability of random linear codes over small fields, both from errors and from erasures. We consider codes of rate $\epsilon$-close to capacity, and aim to bound the dependence of the output list size $L$ on $\epsilon$, the input list size $\ell$, and the alphabet size $q$. Prior to our work, the best upper bound was $L = q^{O(\ell/\epsilon)}$ (Zyablov and Pinsker, Prob. Per. Inf. 1981). Previous work has identified cases in which linear codes provably perform worse than non-linear codes with respect to list-recovery. While there exist non-linear codes that achieve $L=O(\ell/\epsilon)$, we know that $L \ge \ell^{\Omega(1/\epsilon)}$ is necessary for list recovery from erasures over fields of small characteristic, and for list recovery from errors over large alphabets. We show that in other relevant regimes there is no significant price to pay for linearity, in the sense that we get the correct dependence on the gap-to-capacity $\epsilon$ and go beyond the Zyablov-Pinsker bound for the first time. Specifically, when $q$ is constant and $\epsilon$ approaches zero: - For list-recovery from erasures over prime fields, we show that $L \leq C_1/\epsilon$. By prior work, such a result cannot be obtained for low-characteristic fields. - For list-recovery from errors over arbitrary fields, we prove that $L \leq C_2/\epsilon$. Above, $C_1$ and $C_2$ depend on the decoding radius, input list size, and field size. We provide concrete bounds on the constants above, and the upper bounds on $L$ improve upon the Zyablov-Pinsker bound whenever $q\leq 2^{(1/\epsilon)^c}$ for some small universal constant $c>0$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 37 canonical work pages

  1. [1]

    Near-optimal erasure list-decodable codes

    Avraham Ben-Aroya , Dean Doron, and Amnon Ta-Shma . Near-optimal erasure list-decodable codes. In 35th Computational Complexity Conference (CCC) , pages 1:1--1:27. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2020

    work page 2020

  2. [2]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas. Elements of Information Theory . John Wiley & Sons, 2nd edition, 2006

    work page 2006

  3. [3]

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

    Yeyuan Chen and Zihan Zhang. Explicit folded Reed-Solomon and multiplicity codes achieve relaxed generalized Singleton bounds, 2024. https://arxiv.org/abs/2408.15925

    arXiv 2024

  4. [4]

    Nearly optimal pseudorandomness from hardness

    Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. Journal of the ACM , 69(6), November 2022

    work page 2022

  5. [5]

    High-probability list-recovery, and applications to heavy hitters

    Dean Doron and Mary Wootters. High-probability list-recovery, and applications to heavy hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 55:1--55:17. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2022

    work page 2022

  6. [6]

    List decoding for noisy channels, 1957

    Peter Elias. List decoding for noisy channels, 1957. https://dspace.mit.edu/handle/1721.1/4484

    work page 1957

  7. [7]

    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. Preliminary version at STOC 2010

    work page 2011

  8. [8]

    Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets

    Venkatesan Guruswami and Piotr Indyk. Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In 34th Annual Symposium on Theory of Computing (STOC) , pages 812--821. ACM, 2002

    work page 2002

Show all 41 references
  1. [9]

    Linear time encodable and list decodable codes

    Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes. In 35th Annual Symposium on Theory of Computing (STOC) , pages 126--135. ACM, 2003

    2003

  2. [10]

    Efficiently decodable codes meeting G ilbert- V arshamov bound for low rates

    Venkatesan Guruswami and Piotr Indyk. Efficiently decodable codes meeting G ilbert- V arshamov bound for low rates. In 15th Annual Symposium on Discrete Algorithms (SODA) , pages 756--757. SIAM, 2004

    2004

  3. [11]

    Linear-time encodable/decodable codes with near-optimal rate

    Venkatesan Guruswami and Piotr Indyk. Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory , 51(10):3393--3400, 2005

    2005

  4. [12]

    Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound

    Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound. IEEE Transactions on Information Theory , 64(8):5813--5831, 2018

    2018

  5. [13]

    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, 2022

    2022

  6. [14]

    Gilbert, Yi Li, Ely Porat, and Martin J

    Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. For-all sparse recovery in near-optimal time. ACM Transactions on Algorithms , 13(3):1--26, 2017

    2017

  7. [15]

    Improved list-decodability and list-recoverability of Reed-Solomon codes via tree packings

    Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters. Improved list-decodability and list-recoverability of Reed-Solomon codes via tree packings. In 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 708--719. IEEE , 2021

    2021

  8. [16]

    On the list-decodability of random linear rank-metric codes

    Venkatesan Guruswami and Nicolas Resch. On the list-decodability of random linear rank-metric codes. In International Symposium on Information Theory (ISIT) , pages 1505--1509. IEEE, 2018

    2018

  9. [17]

    Singleton-type bounds for list-decoding and list-recovery, and related results

    Eitan Goldberg, Chong Shangguan, and Itzhak Tamo. Singleton-type bounds for list-decoding and list-recovery, and related results. In International Symposium on Information Theory (ISIT) , pages 2565--2570. IEEE, 2022

    2022

  10. [18]

    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

  11. [19]

    Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM , 56(4):20:1--20:34, 2009

    2009

  12. [20]

    Parallel hashing via list recoverability

    Iftach Haitner, Yuval Ishai, Eran Omri, and Ronen Shaltiel. Parallel hashing via list recoverability. In Advances in Cryptology -- CRYPTO 2015 , pages 173--190. Springer Berlin Heidelberg, 2015

    2015

  13. [21]

    Rothblum

    Justin Holmgren, Alex Lombardi, and Ron D. Rothblum. Fiat–Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge). In 53rd Annual Symposium on Theory of Computing (STOC) , pages 750--760. ACM, 2021

    2021

  14. [22]

    Local list recovery of high-rate tensor codes and applications

    Brett Hemenway, Noga Ron-Zewi , and Mary Wootters. Local list recovery of high-rate tensor codes and applications. SIAM Journal on Computing , 49(4):FOCS17--157, January 2020

    2020

  15. [23]

    Efficiently decodable non-adaptive group testing

    Piotr Indyk, Hung Q.\ Ngo, and Atri Rudra. Efficiently decodable non-adaptive group testing. In 21st Annual Symposium on Discrete Algorithms (SODA) , pages 1126--1142. SIAM, 2010

    2010

  16. [24]

    Let's have both! Optimal list-recoverability via alphabet permutation codes, 2025

    Sergey Komech and Jonathan Mosheiff. Let's have both! Optimal list-recoverability via alphabet permutation codes, 2025. https://www.arxiv.org/abs/2502.05858

    2025 arXiv

  17. [25]

    High-rate locally correctable and locally testable codes with sub-polynomial query complexity

    Swastik Kopparty, Or Meir, Noga Ron-Zewi , and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. Journal of the ACM , 64(2):1--42, 2017

    2017

  18. [26]

    Improved decoding of folded Reed-Solomon and multiplicity codes

    Swastik Kopparty, Noga Ron-Zewi , Shubhangi Saraf, and Mary Wootters. Improved decoding of folded Reed-Solomon and multiplicity codes. In 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 212--223. IEEE, 2018

    2018

  19. [27]

    Unbalanced expanders from multiplicity codes

    Itay Kalev and Amnon Ta-Shma . Unbalanced expanders from multiplicity codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages 12:1--12:14. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Informatik, 2022

    2022

  20. [28]

    Vsevolod F. Lev. Linear equations over F _p and moments of exponential sums . Duke Mathematical Journal , 107(2):239--263, 2001

    2001

  21. [29]

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

    Matan Levi, Jonathan Mosheiff, and Nikhil Shagrithaya. Random Reed-Solomon codes and random linear codes are locally equivalent, 2024. https://arxiv.org/abs/2406.02238

    2024

  22. [30]

    Nguyen, and Mikkel Thorup

    Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, and Mikkel Thorup. Heavy hitters via cluster-preserving clustering. In 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 61--70. IEEE, 2016

    2016

  23. [31]

    On the list recoverability of randomly punctured codes

    Ben Lund and Aditya Potukuchi. On the list recoverability of randomly punctured codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages 30:1--30:11. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2020

    2020

  24. [32]

    Near-optimal list-recovery of linear code families, 2025

    Ray Li and Nikhil Shagrithaya. Near-optimal list-recovery of linear code families, 2025. https://arxiv.org/abs/2502.13877

    2025 arXiv

  25. [33]

    Randomness-efficient constructions of capacity-achieving list-decodable codes, 2024

    Jonathan Mosheiff, Nicolas Resch, Kuo Shang, and Chen Yuan. Randomness-efficient constructions of capacity-achieving list-decodable codes, 2024. https://arxiv.org/abs/2402.11533

    2024 arXiv

  26. [34]

    Efficiently decodable error-correcting list disjunct matrices and applications

    Hung Q.\ Ngo, Ely Porat, and Atri Rudra. Efficiently decodable error-correcting list disjunct matrices and applications. In International Colloquium on Automata, Languages, and Programming (ICALP) , pages 557--568. Springer, 2011

    2011

  27. [35]

    List-Decodable Codes: (Randomized) Constructions and Applications

    Nicolas Resch. List-Decodable Codes: (Randomized) Constructions and Applications . PhD thesis, Carnegie Mellon University, 2020. http://reports-archive.adm.cs.cmu.edu/anon/2020/abstracts/20-113.html

    2020

  28. [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 46th Annual Symposium on Theory of Computing (STOC) , pages 764--773. ACM, 2014

    2014

  29. [37]

    Average-radius list-recoverability of random linear codes

    Atri Rudra and Mary Wootters. Average-radius list-recoverability of random linear codes. In 29th Annual Symposium on Discrete Algorithms (SODA) , pages 644--662. SIAM, 2018

    2018

  30. [38]

    Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes

    Itzhak Tamo. Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes. IEEE Transactions on Information Theory , 70(12):8659--8668, 2024

    2024

  31. [39]

    Extractor codes

    Amnon Ta-Shma and David Zuckerman. Extractor codes. IEEE Transactions on Information Theory , 50(12):3015--3025, 2004

    2004

  32. [40]

    Sequential Decoding

    John Wozencraft and Barney Reiffen. Sequential Decoding . MIT Press, 1961

    1961

  33. [41]

    List concatenated decoding

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

    1981

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.