Friday, October 25, 2019 - 12:00pm to 1:00pm
Location:Traffic21 Classroom 6501 Gates Hillman Centers
Speaker:NICOLAS RESCH, Ph.D. Student http://www.cs.cmu.edu/~nresch/
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.