Combinatorial bounds for list-decoding

Madhu Sudan

EECS and LCS, MIT

October 5,
4:15pm
refreshments at 3:45pm
2-338

ABSTRACT 

For integers n,q,and k, a q-ary error-correcting code (or simply code) of message length k, and block length n, is a collection C, with |C| = q^k, of sequences of length $n$ over the letters {1,..,q}. The Hamming distance between two sequences x and y is the number of coordinates where they differ. A code C has minimum distance at least d if every pair of distinct sequences contained in the code have Hamming distance at least d. The parameter k/n is called the rate of a code, and the parameter d/n is the relative distance of the code.

Error-correcting codes have been studied for over fifty years now due to their immense practical use. The rate and relative distance are the two classical parameters of interest. In this talk we focus on a different parameter ``the list-decoding radius of a code'', and study its behaviour as a function of the more classically studied parameters. We describe the reasons to study this parameter, and some well-known bounds. Time permitting, we will describe some recent work (with V. Guruswami, J. Hastad, and D. Zuckerman), showing the existence of codes with non-trivial list-decoding radii.


Speaker's Contact Info: madhu(at-sign)mit.edu


Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on September 18, 2001 at 04:16 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.