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.
BibTeX - Entry
@InProceedings{wootters:LIPIcs:2020:12674,
author = {Mary Wootters},
title = {{List-Decodability of Structured Ensembles of Codes (Invited Talk)}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {3:1--3:5},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ΔΎ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12674},
URN = {urn:nbn:de:0030-drops-126742},
doi = {10.4230/LIPIcs.MFCS.2020.3},
annote = {Keywords: Error Correcting Codes, List-Decoding}
}
|
Keywords: |
|
Error Correcting Codes, List-Decoding |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)