Spring 2015

List Recovery and Local Decoding of Expander Codes

Thursday, Feb. 12, 2015 11:30 am12:00 pm PST

Add to Calendar


Calvin Lab Auditorium

Expander codes—codes based on expander graphs, introduced by Sipser and Spielman in the 1990's—are notable for their extremely fast (linear) decoding time. In this talk, I'll mention two recent results which show that these old(ish) codes can learn new tricks. First, when appropriately instantiated, they admit sublinear time local decoding algorithms with rate approaching 1. Second, with a different instantiation, they can be list-recovered (a variant on list-decoding) in linear time, with rate again approaching 1.

These are joint works with Rafail Ostrovsky and Brett Hemenway.