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.