Computer Science Speaking Skills Talk

Friday, October 25, 2019 - 12:00pm to 1:00pm


Traffic21 Classroom 6501 Gates Hillman Centers



LDPC Codes Achieve List- Decoding Capacity

We show that Gallagers ensemble of Low-Density Parity Check (LDPC) 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 truly 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 satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallagers distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius listdecoding. Along the way, we give a characterization of sets of codewords that are likely to appear in a random linear code, which may be of independent interest.

Joint work with Jonathan Mosheiff, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

For More Information, Contact:


Speaking Skills