## Select Seminar Series

All seminarsYou are here

- Home
- ›
- Studying at the Faculty
- ›
- Seminars ›
- Upcoming Seminars

# 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 windowWe 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.