V. Guruswami; \\ List Error-Correction Algorithms&Applications:..\\
  • FENS
  • V. Guruswami; \\ List Error-Correction Algorithms&Applications:..\\

You are here

Faculty of Engineering and Natural Sciences







List Error-Correction Algorithms and Applications: A Survey


Professor Venkatesan Guruswami  


Carnegie Mellon University , Computer Science Department


The construction of error-correcting codes that achieve the best possible trade-off between information rate and the amount of errors that can be corrected has been a long sought-after goal. In this talk, I will survey some of our work on list decoding, culminating in the construction of codes with the optimal rate for any desired error-correction radius. I will describe these codes (called folded Reed-Solomon codes), and give a peek into the algebraic ideas underlying their error-correction. The new algorithms correct a factor of two more errors compared to the conventional algorithms currently used in every CD player and desktop PC, as well as many other applications.




List decodable codes have also found surprising applications extraneous to coding theory, in algorithms, complexity theory, and cryptography. I will briefly mention some of these, including a recent construction of unbalanced bipartite graphs with near-optimal expansion


Venkatesan Guruswami received his Bachelor's degree from the Indian Institute of

Technology at Madras in 1997 and his Ph.D. from the Massachusetts Institute of Technology in 2001. He is currently an Associate Professor in the Computer Science Department at

Carnegie Mellon University . From 2002-09, he was a faculty member in the Department of

Computer Science and Engineering at the University of Washington . Dr. Guruswami was a

Miller Research Fellow at the University of California , Berkeley during 2001-02, and was a

member in the School of Mathematics, Institute for Advanced Study during 2007-08.




Dr. Guruswami's research interests span a broad array of topics including the theory of error-correcting codes, approximation algorithms and non-approximability results for NP-hard

optimization problems, explicit combinatorial constructions and pseudorandomness,

probabilistically checkable proofs, computational complexity theory, and algebraic algorithms.

Dr. Guruswami is a recipient of the Computational Complexity Conference best paper award (2007), David and Lucile Packard Foundation Fellowship (2005), Alfred P. Sloan Foundation Fellowship (2005), NSF CAREER award (2004), ACM's Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000).

Dr. Guruswami will be an invited speaker at the International Congress of Mathematicians in Hyderabad , 2010



Monday, Nov. 23, 13.40 - 14.40,  Sabancı University , FENS 2019
Prof. Guruswami's visit is partly supported by TÜBİTAK.