Noga Ron-Zewi
Capacity-achieving Locally List Decodable Codes

Abstract: Locally decodable codes are error-correcting codes admitting
highly efficient sublinear time decoding algorithms, while list
decodable codes are error-correcting codes that can correct extremely
large fraction of errors by outputting a small list of candidate
messages. Starting with the seminal work of Goldreich and Levin,
locally decodable codes and list decodable codes have been two central
objects of study in theoretical computer science. In this talk, I will
describe a recent line of work focused on designing capacity achieving
locally list decodable codes admitting fast sublinear time list
decoding algorithms.

Based on joint works with Brett Hemenway, Swastik Koppary, Shubhangi
Saraf, and Mary Wootters.