Document Open Access Logo

Bounds for List-Decoding and List-Recovery of Random Linear Codes

Authors Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.9.pdf
  • Filesize: 0.57 MB
  • 21 pages

Document Identifiers

Author Details

Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Ray Li
  • Department of Computer Science, Stanford University, CA, USA
Jonathan Mosheiff
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Nicolas Resch
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Shashwat Silas
  • Department of Computer Science, Stanford University, CA, USA
Mary Wootters
  • Department of Computer Science, Stanford University, CA, USA

Funding

  • Guruswami, Venkatesan: Partially funded by NSF grants CCF-1563742 and CCF-1814603.
  • Li, Ray: Partially funded by NSF-CAREER grant CCF-1844628, NSF-BSF grant CCF-1814629, a Sloan Research Fellowship and NSF-GRFP grant DGE-1656518.
  • Mosheiff, Jonathan: Partially funded by NSF grants CCF-1563742 and CCF-1814603.
  • Resch, Nicolas: Partially funded by NSF grants CCF-1563742, CCF-1814603, CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808 and a Sloan Research Fellowship.
  • Silas, Shashwat: Partially funded by NSF-CAREER grant CCF-1844628, NSF-BSF grant CCF-1814629, a Sloan Research Fellowship and a Google Graduate Fellowship.
  • Wootters, Mary: Partially funded by NSF-CAREER grant CCF-1844628, NSF-BSF grant CCF-1814629 and a Sloan Research Fellowship.

Cite As Get BibTex

Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for List-Decoding and List-Recovery of Random Linear Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.9

Abstract

A family of error-correcting codes is list-decodable from error fraction p if, for every code in the family, the number of codewords in any Hamming ball of fractional radius p is less than some integer L that is independent of the code length. It is said to be list-recoverable for input list size 𝓁 if for every sufficiently large subset of codewords (of size L or more), there is a coordinate where the codewords take more than 𝓁 values. The parameter L is said to be the "list size" in either case. The capacity, i.e., the largest possible rate for these notions as the list size L → ∞, is known to be 1-h_q(p) for list-decoding, and 1-log_q 𝓁 for list-recovery, where q is the alphabet size of the code family. 
In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below q is the alphabet size, and ε > 0 is the gap to capacity).  
- A random linear code of rate 1 - log_q(𝓁) - ε requires list size L ≥ 𝓁^{Ω(1/ε)} for list-recovery from input list size 𝓁. This is surprisingly in contrast to completely random codes, where L = O(𝓁/ε) suffices w.h.p.
- A random linear code of rate 1 - h_q(p) - ε requires list size L ≥ ⌊ {h_q(p)/ε+0.99}⌋ for list-decoding from error fraction p, when ε is sufficiently small.
- A random binary linear code of rate 1 - h₂(p) - ε is list-decodable from average error fraction p with list size with L ≤ ⌊ {h₂(p)/ε}⌋ + 2. (The average error version measures the average Hamming distance of the codewords from the center of the Hamming ball, instead of the maximum distance as in list-decoding.) 
The second and third results together precisely pin down the list sizes for binary random linear codes for both list-decoding and average-radius list-decoding to three possible values.
Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset - or some symbol-wise permutation of it - lies in a random linear code with high probability. This uses a recent characterization of (Mosheiff, Resch, Ron-Zewi, Silas, Wootters, 2019) of configurations of codewords that are contained in random linear codes. Our upper bound follows from a refinement of the techniques of (Guruswami, Håstad, Sudan, Zuckerman, 2002) and strengthens a previous result of (Li, Wootters, 2018), which applied to list-decoding rather than average-radius list-decoding.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • list-decoding
  • list-recovery
  • random linear codes
  • coding theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. Annals of Mathematics, 162(3):1335-1351, 2005. Google Scholar
  2. Noga Alon and Michael Krivelevich. The concentration of the chromatic number of random graphs. Combinatorica, 17(3):303-313, 1997. Google Scholar
  3. Eli Ben-Sasson, Swastik Kopparty, and Jaikumar Radhakrishnan. Subspace polynomials and limits to list decoding of reed-solomon codes. IEEE Transactions on Information Theory, 56(1):113-120, 2009. Google Scholar
  4. Vladimir M Blinovsky. Code bounds for multiple packings over a nonbinary finite alphabet. Problems of Information Transmission, 41(1):23-32, 2005. Google Scholar
  5. Volodia M. Blinovsky. Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22(1):7–19, 1986. Google Scholar
  6. Béla Bollobás and Paul Erdös. Cliques in random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 80, pages 419-427. Cambridge University Press, 1976. Google Scholar
  7. Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of fourier matrices and list decodability of random linear codes. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 432-442, 2013. URL: https://doi.org/10.1137/1.9781611973105.31.
  8. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. Technical report, ECCC preprint TR19-099, 2019. Google Scholar
  9. Zeev Dvir and Shachar Lovett. Subspace evasive sets. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 351-358. ACM, 2012. Google Scholar
  10. Peter Elias. List decoding for noisy channels. Wescon Convention Record, Part 2, pages 94-104, 1957. Google Scholar
  11. Peter Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37(1):5-12, 1991. Google Scholar
  12. Robert G. Gallager. Low-density parity-check codes. IRE Trans. Information Theory, 8(1):21-28, 1962. URL: https://doi.org/10.1109/TIT.1962.1057683.
  13. Anna C Gilbert, Hung Q Ngo, Ely Porat, Atri Rudra, and Martin J Strauss. l2/l2-foreach sparse recovery with low risk. In International Colloquium on Automata, Languages, and Programming, pages 461-472. Springer, 2013. Google Scholar
  14. Venkatesan Guruswami. List decoding from erasures: Bounds and code constructions. IEEE Transactions on Information Theory, 49(11):2826-2833, 2003. Google Scholar
  15. Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Trans. Information Theory, 57(2):718-725, 2011. URL: https://doi.org/10.1109/TIT.2010.2095170.
  16. Venkatesan Guruswami, Johan Håstad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. IEEE Trans. Information Theory, 48(5):1021-1034, 2002. URL: https://doi.org/10.1109/18.995539.
  17. Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable codes. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 658-667, 2001. URL: https://doi.org/10.1109/SFCS.2001.959942.
  18. Venkatesan Guruswami and Piotr Indyk. Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 812-821, 2002. Google Scholar
  19. Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 126-135, 2003. Google Scholar
  20. Venkatesan Guruswami and Piotr Indyk. Efficiently decodable codes meeting gilbert-varshamov bound for low rates. In SODA, volume 4, pages 756-757. Citeseer, 2004. Google Scholar
  21. Venkatesan Guruswami and Swastik Kopparty. Explicit subspace designs. Combinatorica, 36(2):161-185, 2016. Google Scholar
  22. Venkatesan Guruswami and Srivatsan Narayanan. Combinatorial limitations of average-radius list-decoding. IEEE Trans. Information Theory, 60(10):5827-5842, 2014. URL: https://doi.org/10.1109/TIT.2014.2343224.
  23. Venkatesan Guruswami and Atri Rudra. Limits to list decoding reed-solomon codes. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 602-609, 2005. Google Scholar
  24. Venkatesan Guruswami and Atri Rudra. Concatenated codes can achieve list-decoding capacity. Electronic Colloquium on Computational Complexity (ECCC), 15(054), 2008. URL: http://eccc.hpi-web.de/eccc-reports/2008/TR08-054/index.html.
  25. Venkatesan Guruswami and Salil P. Vadhan. A lower bound on list size for list decoding. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, pages 318-329, 2005. URL: https://doi.org/10.1007/11538462_27.
  26. Venkatesan Guruswami and Chaoping Xing. Folded codes from function field towers and improved optimal rate list decoding. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 339-350. ACM, 2012. Google Scholar
  27. Venkatesan Guruswami and Chaoping Xing. List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 843-852. ACM, 2013. Google Scholar
  28. Iftach Haitner, Yuval Ishai, Eran Omri, and Ronen Shaltiel. Parallel hashing via list recoverability. In Annual Cryptology Conference, pages 173-190. Springer, 2015. Google Scholar
  29. Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. Local list recovery of high-rate tensor codes & applications. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 204-215. IEEE, 2017. Google Scholar
  30. Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. Information and Computation, 261:202-218, 2018. Google Scholar
  31. Piotr Indyk, Hung Q Ngo, and Atri Rudra. Efficiently decodable non-adaptive group testing. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1126-1142. SIAM, 2010. Google Scholar
  32. Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On list recovery of high-rate tensor codes. Electronic Colloquium on Computational Complexity (ECCC), 2019. URL: https://eccc.weizmann.ac.il/report/2019/080/.
  33. Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, and Mary Wootters. Improved decoding of folded reed-solomon and multiplicity codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 212-223. IEEE, 2018. Google Scholar
  34. Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes. arXiv preprint, 2018. URL: http://arxiv.org/abs/1801.07839.
  35. Tomasz Luczak. A note on the sharp concentration of the chromatic number of random graphs. Combinatorica, 11(3):295-297, 1991. Google Scholar
  36. David W Matula. Employee party problem. In Notices of the American Mathematical Society, volume 19, pages A382-A382. Amer Mathematical Soc 201 Charles St, Providence, RI 02940-2213, 1972. Google Scholar
  37. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. Ldpc codes achieve list decoding capacity. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.06430.
  38. 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, pages 557-568. Springer, 2011. Google Scholar
  39. Oliver Riordan and Nicholas Wormald. The diameter of sparse random graphs. Combinatorics, Probability and Computing, 19(5-6):835-926, 2010. Google Scholar
  40. 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. ACM, 2014. Google Scholar
  41. Atri Rudra and Mary Wootters. It'll probably work out: improved list-decoding through random operations. Electronic Colloquium on Computational Complexity (ECCC), 21:104, 2014. URL: http://eccc.hpi-web.de/report/2014/104.
  42. Atri Rudra and Mary Wootters. Average-radius list-recovery of random linear codes. In Proceedings of the 2018 ACM-SIAM Symposium on Discrete Algorithms, SODA, 2018. Google Scholar
  43. Mary Wootters. On the list decodability of random linear codes with large error rates. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 853-860, 2013. URL: https://doi.org/10.1145/2488608.2488716.
  44. Jack Wozencraft. List decoding. Quarter Progress Report, 48:90-95, 1958. Google Scholar
  45. Victor Vasilievich Zyablov and Mark Semenovich Pinsker. List concatenated decoding. Problemy Peredachi Informatsii, 17(4):29-33, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact