| Title | List Decoding of Error-Correcting Codes: Recent Progress and Challenges Ahead |
| Speaker | Prof. Venkatesan Guruswami, University of Washington |
| Web page | Venkatesan Guruswami |
| Time | Monday, November 8, 11:00am |
| Location | MHP 106 |
List decoding is the problem of finding all codewords of an error-correcting code that are within a certain distance of the received word. Though introduced independently by Elias and Wozencraft in the late 50's, only recently has progress been made on the development of efficient list decoding algorithms. List decoding permits recovery beyond that possible using classical unique decoding algorithms, and enables approaching capacity even when the noise model is "adversarial" as opposed to obeying an assumed probabilistic model. This talk is a survey into the subject of list decoding --- it will briefly discuss the combinatorial results that indicate the potential of list decoding and set the stage for new algorithmic questions, followed by a peek into some of substantial recent progress on the algorithmic front. The talk will also highlight several intriguing challenges (combinatorial, algorithmic, and complexity-theoretic) concerning list decoding that lie ahead of us.