Combinatorial bounds for listdecodingMadhu SudanEECS and LCS, MIT
October 5,

ABSTRACT


For integers n,q,and k, a qary errorcorrecting 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. Errorcorrecting 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 listdecoding 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 wellknown bounds. Time permitting, we will describe some recent work (with V. Guruswami, J. Hastad, and D. Zuckerman), showing the existence of codes with nontrivial listdecoding radii. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

