Document Open Access Logo

List-Decodability of Structured Ensembles of Codes (Invited Talk)

Author Mary Wootters

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.3.pdf
  • Filesize: 364 kB
  • 5 pages

Document Identifiers

Author Details

Mary Wootters
  • Stanford University, CA, USA

Acknowledgements

This invited talk is based on the work [Guruswami et al., 2020], co-authored with Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas; and on the work [Mosheiff et al., 2019], co-authored with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, and Shashwat Silas.

Cite AsGet BibTex

Mary Wootters. List-Decodability of Structured Ensembles of Codes (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.3

Abstract

What combinatorial properties are satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball? What about any cube? In this talk, I will discuss the answer to these questions, along with a more general characterization of the properties that are likely to be satisfied by a random subspace. The motivation for this characterization comes from error correcting codes. I will discuss how to use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes. This talk is based on the works [Mosheiff et al., 2019] and [Guruswami et al., 2020], which are joint works with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Error Correcting Codes
  • List-Decoding

Metrics

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

References

  1. 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.
  2. Peter Elias. List decoding for noisy channels. Wescon Convention Record, Part 2, pages 94-104, 1957. Google Scholar
  3. 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.
  4. 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.
  5. Venkatesan Guruswami and Piotr Indyk. Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. In SODA, volume 4, pages 756-757, 2004. Google Scholar
  6. Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes. arXiv preprint arXiv:2004.13247, 2020. To appear, RANDOM 2020. Google Scholar
  7. 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.
  8. 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
  9. Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes. Information and Computation, 261:202-218, 2018. Google Scholar
  10. Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  11. Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. LDPC codes achieve list decoding capacity. arXiv preprint arXiv:1909.06430, 2019. Google Scholar
  12. 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
  13. 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
  14. Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957. Google Scholar
  15. 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.
  16. Jack Wozencraft. List decoding. Quarter Progress Report, 48:90-95, 1958. Google Scholar
  17. 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 Imprint Privacy Contact