List Decoding Expander-Based Codes (up to capacity, in near-linear time)

We will talk about a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. These constructions often proceed by showing that the distance of local constant-sized codes can be lifted to a distance lower bound for the global code. The regularity framework allows us to similarly lift list size bounds for local base codes, to list size bounds for the global codes.

 

This allows us to obtain novel combinatorial bounds for list decoding and list recovery up to optimal radius, for Tanner codes of Sipser and Spielman, and for the distance amplification scheme of Alon, Edmonds, and Luby. Further, using existing algorithms for computing weak-regularity decompositions of sparse graphs, these tasks can be performed in (randomized) near-linear time.

 

Based on joint work with Shashank Srivastava.