List Decoding Expander-Based Codes up to Capacity in Near-Linear Time

We give a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. Using existing algorithms for computing regularity decompositions of sparse graphs in (randomized) near-linear time, and appropriate choices for the constant-sized inner/base codes, we prove the following:–Expander-based codes constructed using the distance amplification technique of Alon, Edmonds and Luby [FOCS 1995] can be list decoded to capacity in near-linear time. By known results, the output list is optimal up to constant factors.–The same codes of Alon, Edmonds and Luby, can also be list recovered to capacity in near-linear time, with constant-sized output lists.–The Tanner code construction of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] can be list decoded to its distance in near-linear time, with constant-sized output lists.Our results imply novel combinatorial as well as algorithmic bounds for each of the above explicit constructions. All of these bounds are obtained via combinatorial rigidity phenomena, proved using (weak) graph regularity. The regularity framework allows us to lift the list decoding and list recovery properties for the local base codes, to the global codes obtained via the above constructions.