Description
TITLE: Progress in Error-Correction: A Survey
Speaker: Venkatesan Guruswami, Carnegie Mellon Univ.
ABSTRACT:
Error-correcting codes play a crucial role in safeguarding data against the
adverse effects of noise during communication and storage. They are also
powerful tools underlying several recent advances in theoretical computer
science and combinatorics. The central challenge in coding theory is to
construct codes with minimum possible redundancy for different error models
and requirements on the decoder, along with efficient algorithms for
error-correction using those codes. Much progress has been made toward this
quest in the nearly seven decades since the birth of coding theory. Several
fundamental problems, however, continue to challenge us, and exciting new
directions routinely emerge to address current technological demands as well
as applications in computational complexity and cryptography. This talk will
survey some of our recent works on error-correction in various models, such
as:
- worst-case errors, where we construct list decodable codes with redundancy
as small as the target error fraction;
- i.i.d. errors, where we show polar codes enable efficient error-correction
even as the redundancy approaches Shannon capacity;
- bit deletions, where we give codes that can correct the largest known
fraction of deletions;
- single symbol erasure, a model of substantial current interest for
tackling node failures in distributed storage, where we give novel repair
algorithms for Reed-Solomon codes as well as simple new codes with
low-bandwidth repair mechanisms.