List Decoding - Algebraic and Combinatorial

Explore the theory of error-correcting codes through this comprehensive seminar focusing on list decoding techniques and their applications in pseudorandomness and complexity theory. Learn about classical constructions of optimally list decodable codes, particularly the groundbreaking work by Guruswami and Rudra on Folded Reed-Solomon Codes based on bounded degree polynomials over finite fields. Discover the significant structural and algorithmic breakthroughs that have emerged in recent years, building upon two decades of research since these codes were first introduced. Examine how expander graph-based codes have recently been shown to share similar features with algebraic codes, and understand the common proof techniques that suggest a broader underlying theory connecting these different approaches to list decoding. Gain insights into cutting-edge research developments that bridge algebraic and combinatorial methods in coding theory, presented as part of the Computer Science/Discrete Mathematics Seminar series.