Document Open Access Logo

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

Author Mary Wootters

PDF

File

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

Document Identifiers

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

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.

Cite As Get 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

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.

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact