Name
Abstract | ||
|---|---|---|
We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property P, there is some R* so that random linear codes of rate slightly less than R* satisfy P with high probability, while random linear codes of rate slightly more than R* with high probability do not. We also give a characterization of the threshold rate R*. This is an extended abstract. The full version is available at https://arxiv.org/abs/1909.06430 |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/FOCS46700.2020.00050 | 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | Volume |
LDPC, List Decoding, Local Property, Thershold | Conference | 26 |
ISSN | ISBN | Citations |
1523-8288 | 978-1-7281-9622-0 | 1 |
PageRank | References | Authors |
0.38 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jonathan Mosheiff | 1 | 1 | 1.73 |
| Nicolas Resch | 2 | 4 | 2.80 |
| Noga Ron-Zewi | 3 | 40 | 9.89 |
| Shashwat Silas | 4 | 2 | 1.40 |
| Mary Wootters | 5 | 172 | 25.99 |