| Title | : | A few options go a long way: List decoding and applications |
| Speaker | : | Prof. Venkatesan Guruswami (UC Berkeley) |
| Details | : | Tue, 7 Jan, 2025 2:30 PM @ SSB 334 |
| Abstract: | : | List decoding is a form of error-correction that allows the decoding 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 survey-style talk will provide a glimpse of several facets of list decoding, its origins, evolution, constructions, connections, and applications. Speaker Bio: Prof. Venkatesan Guruswami is the Chancellor's Professor at the Dept. of EECS, UC Berkeley. He is also a Senior Scientist and Interim Director at Simons Institute for the Theory of Computing. Dr. Guruswami's research interests span several topics in theoretical computer science such as the theory of error-correcting codes, approximability of fundamental optimization problems, explicit combinatorial constructions and pseudorandomness, probabilistically checkable proofs, computational complexity theory, and algebraic algorithms. Dr. Guruswami currently serves as the Editor-in-Chief for the Journal of ACM and has in the past served as the Editor-in-Chief for the ACM Transactions on Computation Theory. Dr. Guruswami is a recipient of the Presburger Award (2012), Packard Fellowship (2005), Sloan Fellowship (2005), NSF CAREER award (2004), the ACM Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000). |
