2026-08-05T03:50:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12674 2024-03-12T11:59:29Z ddc:004 open_access

List-Decodability of Structured Ensembles of Codes (Invited Talk) Wootters, Mary Error Correcting Codes List-Decoding 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mary Wootters 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.3 urn:nbn:de:0030-drops-126742 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.3 eng https://creativecommons.org/licenses/by/3.0/legalcode