A Few Options Go a Long Way: List Decoding and Applications | Richard M. Karp Distinguished Lecture

List decoding allows the error-correction procedure to output a small list of candidate codewords, and the decoding is deemed successful if the list includes the original uncorrupted codeword. List decoding has enjoyed a number of influential consequences. It allows bridging between the Shannon and Hamming worlds and achieving "capacity" even in worst-case error models. It serves as a versatile subroutine in varied error-correction scenarios not directly tied to list decoding. It boasts a diverse array of "extraneous" applications in computational complexity, combinatorics, cryptography, and quantum computing. And it has infused several novel algebraic, probabilistic, combinatorial, and algorithmic techniques and challenges into coding theory.

In this survey talk, Venkatesan Guruswami will aim to provide a glimpse of several facets of list decoding, its origins, evolution, constructions, connections, and applications.

Venkatesan Guruswami is a senior scientist at the Simons Institute and a professor in the Departments of EECS and Mathematics at UC Berkeley. His research interests span many areas of theoretical computer science and related mathematics, including error correction, approximate optimization, pseudorandomness, and computational complexity. His latest ventures include promise constraint satisfaction, parameterized complexity, and quantum error correction.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.

Light refreshments will be available prior to the start of the lecture. 

The lecture recording URL will be emailed to registered participants. This URL can be used for immediate access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about 12 to 15 days following each presentation unless otherwise noted.

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.