ICTS:31736

Video URL

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

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

(2025). List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. SciVideos. https://youtu.be/w5gTMH9uAzU

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. SciVideos, May. 05, 2025, https://youtu.be/w5gTMH9uAzU 

          @misc{ scivideos_ICTS:31736,
            doi = {},
            url = {https://youtu.be/w5gTMH9uAzU},
            author = {},
            keywords = {},
            language = {en},
            title = {List Decoding Expander-Based Codes up to Capacity in Near-Linear Time},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31736 see, \url{https://scivideos.org/icts-tifr/31736}}
          }
Shashank Srivastava
Talk numberICTS:31736
Source RepositoryICTS-TIFR

Abstract

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 in (randomized) near-linear time, these tasks can be performed in near-linear time.

Based on joint work with Madhur Tulsiani.
DIMACS (Rutgers University) and Institute for Advanced