You are here

Foundations of Computer Science Colloquium

MondayJun 21, 202111:15
Foundations of Computer Science ColloquiumRoom 155
Speaker:Noga Ron-ZewiTitle:LDPC Codes Achieve List Decoding CapacityAbstract:opens in new windowin html    pdfopens in new window
We show that random Low-Density Parity Check (LDPC) codes achieve list decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result follows from two other more general results that may be of independent interest: 1. A simple characterization of the threshold for when ‘local’ combinatorial properties are likely to be satisfied by a random subspace over a finite field. 2. Any ‘local’ property that is satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code. Based on joint work with Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters.