LIPIcs.APPROX-RANDOM.2020.30.pdf
- Filesize: 449 kB
- 11 pages
Document
On the List Recoverability of Randomly Punctured Codes
Authors
Ben Lund 
,
Aditya Potukuchi
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-11
File
Document Identifiers
Author Details
Acknowledgements
We thank Venkat Guruswami, Jeff Kahn, Swastik Kopparty, Noga Ron-Zewi, and Mary Wootters for helpful discussions. We also thank an anonymous reviewer for helpful comments on the presentation of the results.
Cite AsGet BibTex
Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.30
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.30
Abstract
We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.
Subject Classification
ACM Subject Classification
- Theory of computation → Error-correcting codes
Keywords
- List recovery
- randomly punctured codes
- Reed-Solomon codes
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Xue Chen. personal communication.
- Xue Chen and David Zuckerman. Existence of simple extractors. Electronic Colloquium on Computational Complexity (ECCC), 25:116, 2018. URL: https://eccc.weizmann.ac.il/report/2018/116.
-
Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009.
- Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound. IEEE Trans. Information Theory, 64(8):5813-5831, 2018. URL: https://doi.org/10.1109/TIT.2018.2809788.
-
Venkatesan Guruswami. personal communication.
- Venkatesan Guruswami. Algorithmic results in list decoding. Foundations and Trends in Theoretical Computer Science, 2(2), 2006. URL: https://doi.org/10.1561/0400000007.
-
Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable codes. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 658-667. IEEE, 2001.
- Venkatesan Guruswami and Atri Rudra. Limits to list decoding Reed-Solomon codes. IEEE Trans. Information Theory, 52(8):3642-3649, 2006. URL: https://doi.org/10.1109/TIT.2006.878164.
- Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. J. ACM, 56(4):20:1-20:34, 2009. URL: https://doi.org/10.1145/1538902.1538904.
- Atri Rudra and Mary Wootters. Every list-decodable code for high noise has abundant near-optimal rate puncturings. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 764-773, 2014. URL: https://doi.org/10.1145/2591796.2591797.
- Atri Rudra and Mary Wootters. It'll probably work out: Improved list-decoding through random operations. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 287-296, 2015. URL: https://doi.org/10.1145/2688073.2688092.
- Salil P. Vadhan. The unified theory of pseudorandomness: guest column. SIGACT News, 38(3):39-54, 2007. URL: https://doi.org/10.1145/1324215.1324225.