Research Briefing
cs.IT 2605.30101v1 must_read

List Recovery for Random Low-Rate Linear Codes

Isaac M Hair, Amit Sahai

Published 2026-05-28 15:43:45 相关性 1.0000 价值 0.8300 cs.IT
arXiv PDF HTML

摘要

选中正文可添加批注

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension $d$, error fraction $α$, and accuracy parameter $\varepsilon$, a random $d$-dimensional linear code $C \subseteq \mathbb{F}_p^n$ is, with high probability, $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable simultaneously for all input list sizes $\ell\le 2^{O_{α, \varepsilon, d}(n/\log n)}$. The proof is inspired by work of Matoušek, Přívětivý, and Škovroň on reconstructing point sets from their projections. It combines a deterministic graph-theoretic certificate, a nonvanishing determinant criterion, and the Schwartz--Zippel lemma. We also give a lower bound showing that any linear code $C \subseteq \mathbb{F}_p^n$ of dimension at least two cannot be $(α,\ell,\frac{1+\varepsilon}{1-α}\ell)$-list recoverable for feasible list sizes $\ell \geq 2^{Ω_{α, \varepsilon}(n)}$. In this sense, our result is nearly optimal.

相关性判断

high
相关方向
coding_theory list_recovery list_decoding
判断依据

Directly about list recovery for random linear codes over finite fields, a core coding theory topic closely tied to list decoding and capacity phenomena.

价值判断

High relevance to core cs.IT coding theory, specifically list recovery and random linear codes. Claims appear technically substantial: simultaneous list recovery up to subexponential list sizes with near-optimal lower bound evidence. Structure analysis identifies concrete proof machinery rather than only abstract-level claims.

核心问题与主要方法

核心问题

List recovery of random low-rate linear codes over finite fields

场景：Fixed-dimension d random linear codes C ⊆ F_p^n over sufficiently large prime fields, with n growing and low-rate regime

主要方法

A list-recovery counterexample is transformed into a colored multigraph: vertices are messages, coordinate colors form matchings inside fibers of λ_i, and matching edges encode homogeneous linear constraints. A graph-theoretic certificate extracts d spanning trees with pairwise disjoint color sets from sufficiently many large colored matchings. The spanning-tree equations define a square linear system on point differences; disjoint color sets allow a specialization showing the determinant polynomial is nonzero. Schwartz-Zippel bounds the probability that random coordinate forms annihilate any fixed certificate, and a union bound over certificates yields high-probability goodness up to size B. Conditioning a random n by d linear map on full rank converts the random matrix result into a statement about uniformly random d-dimensional linear codes. The lower bound uses a two-dimensional subcode and a generalized arithmetic box with small coordinate projections but too many codewords for the target list size.

关键贡献与后续阅读

关键贡献

Establishes simultaneous list recovery for random fixed-dimension linear codes over sufficiently large prime fields with output list size ((1+ε)/(1-α))ℓ for all input list sizes up to 2^{δ n/log n}. Provides an explicit near-optimality statement: every linear code of dimension at least two fails the same list-recovery guarantee for feasible list sizes ℓ in an exponential range ℓ≥2^{δ n}. Introduces a proof route from list-recovery failure to colored matching graphs and then to d color-disjoint spanning-tree certificates. Develops an algebraic certificate based on a nonvanishing determinant polynomial whose nonzero evaluation forces all certificate points to coincide, contradicting distinctness of the bad message set. Combines deterministic certificate avoidance with Schwartz-Zippel and a certificate union bound to prove the random-code guarantee, then conditions on full rank to obtain uniform random subspaces.

研究启发

How large is the computable field-size threshold f(n) in usable terms, and is it only a proof artifact of the union bound over certificates? Can the exponent range 2^{δ n/log n} be improved toward 2^{c n}, or does the lower bound indicate an unavoidable qualitative barrier for this output-list constant? Does the determinant-certificate method extend beyond prime fields or beyond fixed dimension d? Are there algorithmic consequences for constructing or certifying such codes, or is the result purely existential/probabilistic?

限制与不确定性

Scope is specialized to sufficiently large prime fields and fixed-dimension low-rate codes, so broader coding-theory impact may be limited. Assessment relies on provided structure analysis only, not independent full-paper verification.

原文信息

正文记录 1
参考文献 16
最近更新 2026-05-30 13:21
查看正文预览 
Abstract

Content selection saved. Describe the issue below:

List recovery for random low-rate linear codes

We prove a list recovery guarantee for random low-rate linear codes over sufficiently large prime fields. For fixed dimension d d , error fraction α \alpha , and accuracy parameter ε \varepsilon , a random d d -dimensional linear code C ⊆ 𝔽 p n C\subseteq\mathbb{F}_{p}^{n} is, with high probability, ( α , ℓ , 1 + ε 1 − α ​ ℓ ) (\alpha,\ell,\frac{1+\varepsilon}{1-\alpha}\ell) -list recoverable simultaneously for all input list sizes ℓ ≤ 2 O α , ε , d ​ ( n / log ⁡ n ) \ell\leq 2^{O_{\alpha,\varepsilon,d}(n/\log n)} . The proof is inspired by a work of Matoušek, Přívětivý, and Škovroň on reconstructing point sets from their projections. It combines a deterministic graph-theoretic certificate, a nonvanishing determinant criterion, and the Schwartz–Zippel lemma. We also give a lower bound showing that any linear code C ⊆ 𝔽 p n C\subseteq\mathbb{F}_{p}^{n} of dimension at least two cannot be ( α , ℓ , 1 + ε 1 − α ​ ℓ ) (\alpha,\ell,\frac{1+\varepsilon}{1-\alpha}\ell) -list recoverable for feasible list sizes ℓ ≥ 2 Ω α , ε ​ ( n ) \ell\geq 2^{\Omega_{\alpha,\varepsilon}(n)} . In
查看参考文献
  1. [BCDZ25] Joshua Brakensiek, Yeyuan Chen, Manik Dhar, and Zihan Zhang, Combinatorial Bounds for List Recovery via Discrete Brascamp–Lieb Inequalities , arXiv:2510.13775, 2025.
  2. [DMRR25] Dean Doron, Jonathan Mosheiff, Nicolas Resch, and João Ribeiro, List-Recovery of Random Linear Codes over Small Fields , in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) , LIPIcs, vol. 353, 57:1–57:18, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.57.
  3. [GLM+22] 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 (2022), no. 2, 923–939. doi:10.1109/TIT.2021.3127126.
  4. [GHK11] Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty, On the List-Decodability of Random Linear Codes , IEEE Transactions on Information Theory 57 (2011), no. 2, 718–725. doi:10.1109/TIT.2010.2095170.
  5. [GS99] Venkatesan Guruswami and Madhu Sudan, Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes , IEEE Transactions on Information Theory 45 (1999), no. 6, 1757–1767. doi:10.1109/18.782097.
  6. [HRW20] Brett Hemenway, Noga Ron-Zewi, and Mary Wootters, Local List Recovery of High-Rate Tensor Codes and Applications , SIAM Journal on Computing 49 (2020), no. 4, FOCS17-157–FOCS17-195. doi:10.1137/17M116149X.
  7. [LS25] 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) , LIPIcs, vol. 353, 53:1–53:14, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.53.
  8. [MPS08] Jiří Matoušek, Aleš Přívětivý, and Petr Škovroň, How Many Points Can Be Reconstructed from k k Projections? , SIAM Journal on Discrete Mathematics 22 (2008), no. 4, 1605–1623. doi:10.1137/080715706.
  9. [RV25] Nicolas Resch and S. Venkitesh, List Recoverable Codes: The Good, the Bad, and the Unknown (hopefully not Ugly) , arXiv:2510.07597, 2025.
  10. [RYZ23] Nicolas Resch, Chen Yuan, and Yihan Zhang, Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery , in 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , LIPIcs, vol. 261, 99:1–99:18, 2023. doi:10.4230/LIPIcs.ICALP.2023.99.
  11. [RW18] 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 (SODA) , 2018, 644–662. doi:10.1137/1.9781611975031.42.
  12. [Woo13] 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 (STOC) , 2013, 853–860. doi:10.1145/2488608.2488716.
  13. [ZP81] V. V. Zyablov and M. S. Pinsker, List concatenated decoding , Problemy Peredachi Informatsii 17 (1981), no. 4, 29–33.
  14. [Sch80] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities , Journal of the ACM 27 (1980), no. 4, 701–717.
  15. [Zip79] R. Zippel, Probabilistic algorithms for sparse polynomials , in Symbolic and Algebraic Computation , EUROSAM 1979, Lecture Notes in Computer Science, vol. 72, Springer, 1979, 216–226.
  16. [ZHC+26] Junyi Zhang * , Xinjie He * , Hyunsik Chae, Ethan Ji, Eric Jiang, Rushil Raghavan, Yiwen Kou, Alex Taylor, Kai-Wei Chang † , Raghu Meka † , Violet Peng † , Amit Sahai † , Terence Tao † , and Wei Wang † . UCLA Moonshot Harness . 2026. * Co-first authors with equal contribution. The remaining students are ordered by contribution to the harness. † Principal investigators, listed at the end in alphabetical order by last name.