Old Problems and New Results in Coding Theory

Alexander Vardy, University of California, San Diego

Coding theory was born in 1948 with the work of Claude Shannon, who proved that for every information rate R up to channel capacity, there exists a code of rate R that guarantees a vanishing probability of decoding error. Shannon, however, did not tell us how to find such codes no how to decode them.

It was recognized early on that codes with good Hamming distance can correct many errors, while codes endowed with algebraic structure admit efficient algebraic decoding algorithms. This has led to over 50 years of research in algebraic and combinatorial coding theory. We will survey several key problems and new results in this area. In particular, we'll elaborate upon a new asymptotic improvement of the Gilbert-Varshamov bound and upon recent methods for decoding Reed-Solomon codes using bivariate polynomial interpolation.

About ten years ago, the field of coding theory was transformed by the discovery of codes defined on certain graphs, with no algebraic structure, that perform extremely close to the Shannon capacity under probabilistic message-passing decoding. We will briefly review this exciting development, and point out the challenges that lie ahead in the area of "probabilistic" coding theory.

BIOGRAPHY: Alexander Vardy is a Professor in the Department of Electrical Engineering, the Department of Computer Science, and the Department of Mathematics at the University of California, San Diego. He has over 150 publications and numerous patents, most of them in the general area of coding theory and practice. He received the Rothschild Fellowship in 1992, the IBM Invention Achievement Award in 1993, the Xerox Award for faculty research in 1996, the Information Theory Society Paper Award in 2004, and the Best Paper Award at the Symposium on Foundations of Computer Science (FOCS) in 2005. He is a Packard Foundation Fellow and a Fellow of the Institute of Electrical and Electronics Engineers (IEEE). During 1995-2001, he was Associate Editor for Coding Theory, and then the Editor-in-Chief of the IEEE Transactions on Information Theory. He currently serves on the editorial board of the SIAM Journal on Discrete Math and on the Board of Governors of the IEEE Information Theory Society. He speaks Russian, Hebrew, French, and some Japanese (but will present the Colloquium talk in English).

The P/T Colloquium is
typically held each
Thursday, 3:45–5:00 PM.

Collaborations 3:15 PM.