Document Open Access Logo

Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

Authors Nicolas Resch , Chen Yuan , Yihan Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.99.pdf
  • Filesize: 1.08 MB
  • 18 pages

Document Identifiers

Author Details

Nicolas Resch
  • Informatics' Institute, University of Amsterdam, The Netherlands
Chen Yuan
  • School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, China
Yihan Zhang
  • Institute of Science and Technology Austria, Klosterneuburg, Austria

Funding

  • Resch, Nicolas: Research supported in part by ERC H2020 grant No.74079 (ALGSTRONGCRYPTO).
  • Yuan, Chen: Research supported in part by the National Key Research and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.

Acknowledgements

YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions.

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.99

Abstract

In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,𝓁,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length 𝓁 and again stipulate that there be less than L codewords. Our main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,𝓁,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a "Plotkin bound." To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Coding theory
  • List-decoding
  • List-recovery
  • Zero-rate thresholds

Metrics

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

Related Versions

References

  1. Noga Alon, Boris Bukh, and Yury Polyanskiy. List-decodable zero-rate codes. IEEE Transactions on Information Theory, 65(3):1657-1667, 2018. Google Scholar
  2. Erdal Arikan. Upper bound on the zero-error list-coding capacity. Information Theory, IEEE Transactions on, 40:1237-1240, August 1994. URL: https://doi.org/10.1109/18.335947.
  3. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complex., 3:307-318, 1993. URL: https://doi.org/10.1007/BF01275486.
  4. L. A. Bassalygo. New upper bounds for error-correcting codes. Probl. of Info. Transm., 1:32-35, 1965. Google Scholar
  5. Vladimir M Blinovsky. Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22:7-19, 1986. Google Scholar
  6. Vladimir M Blinovsky. Code bounds for multiple packings over a nonbinary finite alphabet. Problems of Information Transmission, 41:23-32, 2005. Google Scholar
  7. Vladimir M Blinovsky. On the convexity of one coding-theory function. Problems of Information Transmission, 44:34-39, 2008. Google Scholar
  8. Volodia Blinovsky. Asymptotic combinatorial coding theory, volume 415 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, MA, 1997. URL: https://doi.org/10.1007/978-1-4615-6193-4.
  9. Marco Bondaschi and Marco Dalai. A revisitation of low-rate bounds on the reliability function of discrete memoryless channels for list decoding. IEEE Transactions on Information Theory, 68(5):2829-2838, 2022. URL: https://doi.org/10.1109/TIT.2022.3145318.
  10. Simone Costa and Marco Dalai. New bounds for perfect k-hashing. CoRR, abs/2002.11025, 2020. URL: https://arxiv.org/abs/2002.11025.
  11. M. Dalai, V. G. Carnegie, and J. Radhakrishnan. An improved bound on the zero-error list-decoding capacity of the 4/3 channel. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 1658-1662, June 2017. URL: https://doi.org/10.1109/ISIT.2017.8006811.
  12. Stefano Della Fiore, Simone Costa, and Marco Dalai. Improved bounds for (b, k)-hashing. IEEE Transactions on Information Theory, 68(8):4983-4997, 2022. URL: https://doi.org/10.1109/TIT.2022.3167608.
  13. Philippe Delsarte. An algebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl., 10:vi+-97, 1973. Google Scholar
  14. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1057-1068. IEEE, 2020. Google Scholar
  15. Dean Doron and Mary Wootters. High-probability list-recovery, and applications to heavy hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  16. Peter Elias. List decoding for noisy channels. Wescon Convention Record, Part 2, pages 94-104, 1957. Google Scholar
  17. Peter Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37(1):5-12, 1991. Google Scholar
  18. M. Fredman and J. Komlós. On the size of separating systems and families of perfect hash functions. SIAM Journal on Algebraic Discrete Methods, 5(1):61-68, 1984. URL: https://doi.org/10.1137/0605009.
  19. Edgar N Gilbert. A comparison of signalling alphabets. The Bell System Technical Journal, 31(3):504-522, 1952. Google Scholar
  20. Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), pages 25-32. ACM, 1989. Google Scholar
  21. 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.
  22. 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
  23. 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
  24. 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
  25. 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. URL: https://doi.org/10.1109/TIT.2021.3127126.
  26. Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Threshold rates for properties of random codes. IEEE Transactions on Information Theory, 68(2):905-922, 2022. URL: https://doi.org/10.1109/TIT.2021.3123497.
  27. Venkatesan Guruswami and Andrii Riazanov. Beating Fredman-Komlós for Perfect k-Hashing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 92:1-92:14, Dagstuhl, Germany, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.92.
  28. Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Essential coding theory, January 31, 2022. Draft available at URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf.
  29. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. Journal of the ACM (JACM), 56(4):1-34, 2009. Google Scholar
  30. 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
  31. Justin Holmgren, Alex Lombardi, and Ron D Rothblum. Fiat-shamir via list-recoverable codes (or: parallel repetition of gmw is not zero-knowledge). In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 750-760, 2021. Google Scholar
  32. 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
  33. Jeffrey C Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414-440, 1997. Google Scholar
  34. J. Körner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In Transactions of the Sixth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes (Tech Univ., Prague, 1971; dedicated to the memory of Antonín Špaček), pages 411-425. Academia, Prague, 1973. Google Scholar
  35. J. Körner. Fredman-komlós bounds and information theory. SIAM Journal on Algebraic Discrete Methods, pages 560-570, 1986. Google Scholar
  36. J. Körner and K. Marton. New bounds for perfect hashing via information theory. European Journal of Combinatorics, 9(6):523-530, 1988. URL: https://doi.org/10.1016/S0195-6698(88)80048-9.
  37. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the Fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348, 1993. Google Scholar
  38. Richard J Lipton. Efficient checking of computations. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 207-215. Springer, 1990. Google Scholar
  39. Robert J. McEliece, Eugene R. Rodemich, Howard Rumsey, Jr., and Lloyd R. Welch. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Inform. Theory, IT-23(2):157-166, 1977. URL: https://doi.org/10.1109/tit.1977.1055688.
  40. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. LDPC codes achieve list decoding capacity. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 458-469. IEEE Computer Soc., Los Alamitos, CA, [2020] (C) 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00050.
  41. 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
  42. Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445-450, 1960. Google Scholar
  43. Yury Polyanskiy. Upper bound on list-decoding radius of binary codes. IEEE Transactions on Information Theory, 62(3):1119-1128, 2016. Google Scholar
  44. Nicolas Resch. List-decodable codes:(randomized) constructions and applications. School Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA, Tech. Rep., CMU-CS-20-113, 2020. Google Scholar
  45. Nicolas Resch and Chen Yuan. Threshold rates of code ensembles: Linear is best. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 104:1-104:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.104.
  46. Nicolas Resch, Chen Yuan, and Yihan Zhang. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. CoRR, abs/2210.07754, 2022. URL: https://doi.org/10.48550/arXiv.2210.07754.
  47. Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001. Google Scholar
  48. RR Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957. Google Scholar
  49. Lloyd R. Welch, Robert J. McEliece, and Howard Rumsey, Jr. A low-rate improvement on the Elias bound. IEEE Trans. Inform. Theory, IT-20:676-678, 1974. URL: https://doi.org/10.1109/tit.1974.1055279.
  50. Jack Wozencraft. List decoding. Quarter Progress Report, 48:90-95, 1958. Google Scholar
  51. Chaoping Xing and Chen Yuan. Beating the probabilistic lower bound on perfect hashing. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 33-41. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.3.
  52. Yihan Zhang, Amitalok J. Budkuley, and Sidharth Jaggi. Generalized List Decoding. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1-51:83, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.51.
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 Imprint Privacy Contact