Combinatorial bounds for list-decoding

Madhu Sudan


October 5,
refreshments at 3:45pm


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)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

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