List-decoding is a ubiquitous natural notion in the study of error correcting codes. Gallager's ensemble of Low-Density Parity Check (LDPC) codes is another basic object of high importance. We show that Gallager’s codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. This result opens up a potential avenue towards the construction of linear-time list-decodable codes which achieve list-decoding capacity. Our result on list-decoding follows from a much more general result: any local property (a new notion with regard to codes) satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager’s distribution.

This is a joint work with Nicolas Resch, Noga Ron-Zewi, Shashwat Silas and Mary Wootters.