78 KAM Mathematical Colloquium
Venkatesan Guruswami
(Carnegie Mellon University, USA)
LIST ERROR-CORRECTION ALGORITHMS: A SURVEY
utery 22. listopadu 2011 v 15:40, poslucharna S3, treti patro
KAM MFF UK
Malostranske nam. 25
118 00 Praha 1
Abstract
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 ideas underlying
their error-correction. These list decoding algorithms correct a factor
of two more errors compared to the conventional algorithms
currently used in several storage and communication applications.
List decodable codes have also found several applications
extraneous to coding theory, in algorithms, complexity theory, and
cryptography. Time permitting, I will mention some of these, highlighting
a construction of graphs with good expansion properties.
About speaker
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.
Venkat Guruswami's research interests span several topics including
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 on the editorial boards of the
SIAM Journal on Computing, IEEE Transactions on Information Theory,
and the ACM Transactions on Computation Theory. He is a recipient
of the Packard Fellowship, Sloan Fellowship, NSF CAREER award,
ACM's Doctoral Dissertation Award, and the IEEE Information
Theory Society Paper Award. He was an invited speaker
on the ICM 2010 in Hydarabad.