Low-Density Parity-Check Codes Achieve List-Decoding Capacity

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 toward 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-decodability, list-recoverability, and average-radius list-decodability. 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.