Presenter(s)
ISIT 2024 Plenary Lecture
Date
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.
Biography
Venkatesan Guruswami received his Bachelor's degree in Computer Science from the Indian Institute of Technology at Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. He is currently a Chancellor’s Professor in the Electrical Engineering and Computer Science Department at the University of California, Berkeley, and a senior scientist at the Simons Institute for the Theory of Computing. He was a Miller Research Fellow at UC Berkeley and held faculty positions at the University of Washington and Carnegie Mellon University prior to his current position. His research interests span many topics such as coding and information theory, approximate optimization, computational complexity, pseudo-randomness, and related mathematics. Prof. Guruswami has served the theoretical computer science community in several leadership roles. He is the current Editor-in-Chief of the Journal of the ACM, and was previously Editor-in-Chief of the ACM Transactions on Computation Theory. He has served as the president of the Computational Complexity Foundation and on the editorial boards of JACM, the SIAM Journal on Computing and the IEEE Transactions on Information Theory. He has been program committee chair for the conferences CCC (2012), FOCS (2015), ISIT (2018, co-chair), FSTTCS (2022), and ITCS (2024). Prof. Guruswami is a recipient of a Guggenheim Fellowship, a Simons Investigator award, the Presburger Award, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, an IEEE Information Theory Society Paper Award and a Distinguished Alumnus Award from IIT Madras. He was an invited speaker at the 2010 International Congress of Mathematicians. Prof. Guruswami is a fellow of the ACM, IEEE, and AMS.Related Videos
