A few options go a long way: List decoding and applications

The TCS Group of the Informatics Institute has the pleasure to host the following public lecture on Monday, June 10 from 4-5pm in the CWI Turingzaal. Following the lecture, we will host a reception in the Newtonzaal, where refreshments will be provided.

If you would like to attend, please fill out the following form: https://forms.gle/bHHcBhm1d2ciMNDx9. We hope to see many of you there!

Speaker: Venkatesan Guruswami

Abstract

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.

This talk will provide a glimpse of several facets of list decoding, its origins, evolution, constructions, connections, and applications.

Bio

Venkatesan Guruswami is a Professor of Computer Science and Mathematics at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Venkat received his Bachelor’s degree from the Indian Institute of Technology, Madras, and his Ph.D. from MIT.

Venkat’s research interests include coding theory, constraint satisfaction, approximate optimization, and computational complexity. He is the Editor-in-Chief of JACM, and was previously president of the Computational Complexity Foundation. Venkat is a recipient of the Presburger Award, a Simons Investigator award, Guggenheim, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and a distinguished alumnus award from IIT Madras. He is a fellow of the ACM, IEEE, and AMS