Capacity-Achieving List Decodable Codes for Worst-Case Errors
Speaker: Venkat Guruswami , University of Washington
Date: April 11 2006
Time: 4:15PM to 5:15PM
Location: 32-155
Host: Piotr Indyk, Massachusetts Institute of Technology
Contact: Kevin Matulef, 3-5883, matulef@mit.edu
Relevant URL: http://theory.csail.mit.edu/toc-seminars/An error-correcting code provides a judicious way to encode messages into codewords, incorporating enough redundancy in the process to enable recovery of the message upon receipt of an erroneous codeword. The fundamental trade-off in coding theory is the one between the rate of the code (a measure of amount of redundancy introduced) and the amount of errors that can be corrected. In this talk, we will describe an explicit construction of codes that achieves the optimal trade-off (called "capacity") for a worst-case/adversarial noise model where the channel can corrrupt the codeword arbitrarily subject to a bound on the total number of errors. Previously, capacity-achieving codes were only known for weaker, stochastic models of the channel noise.
Formally, for every 0 < R < 1 and eps > 0, we present an explicit construction of codes of rate R (which encode R.n symbols into n symbols) that can be *list decoded* in polynomial time from up to a fraction (1-R-eps) of errors. Clearly, one needs at least Rn correct symbols in the received word to have any hope of identifying the Rn message symbols, so recovering from (R+eps)n correct symbols is information-theoretically best possible. Our codes are simple to describe: they are certain *folded* Reed-Solomon codes, which are just Reed-Solomon codes, but viewed as a code over a larger alphabet by a careful bundling of codeword symbols.
The talk will introduce and motivate the problem of list decoding, and then give a peek into the algebraic ideas and constructions that lead to the above result. We will also describe some consequences for binary codes and challenging questions that remain open.
Based on joint work with Atri Rudra.
See other events that are part of Theory Colloquium Spring 2006
See other events happening in April 2006
