List decoding of error-correcting codes
Error-correcting codes are combinatorial designs constructed to deal with the problem of noise in information transmission. A code describes how to judiciously add redundancy information so that if a small number of errors occur during transmission, then this can be detected. Furthermore if the number of errors that occur is even smaller, then one can even correct the errors in an information theoretic sense. In the seminal paper that introduced error- correcting codes, Hamming (1950) showed that a code is capable of detecting d errors if and only if it is capable of correcting d/2 errors uniquely. Subsequently the study of error-correcting codes has led to many codes where these tasks are achievable algorithmically. What happens when if we try to recover from more than d/2 errors when the code designed to detect d errors? Hamming's result is often misinterpreted to suggest that this task is ill-posed. However, it turns out that there is a reasonable notion of recovery called ``list- decoding'' dating back to Elias (1957). In this talk we will introduce this notion and describe some recent works that give simple and efficient list-decoding algorithms for one of the most popular family of error-correcting codes. Joint work with Venkatesan Guruswami.