List Decoding Expander-Based Codes in Near-Linear Time

Explore advanced techniques for efficiently decoding expander-based error-correcting codes through this 34-minute conference talk from the ICTS Workshop on High Dimensional Expanders and Codes. Delve into the mathematical foundations and algorithmic approaches for achieving near-linear time complexity in list decoding procedures for codes constructed using expander graphs. Learn about the intersection of graph theory, coding theory, and computational complexity as the speaker presents novel methods for improving decoding efficiency. Examine the theoretical underpinnings of expander-based constructions and their practical implications for error correction in communication systems. Discover how high-dimensional expansion properties can be leveraged to develop faster decoding algorithms while maintaining robust error-correction capabilities. Gain insights into cutting-edge research at the convergence of combinatorics, information theory, and theoretical computer science, presented as part of a comprehensive workshop exploring the latest developments in high-dimensional expanders and error-correcting codes.