Tata Institute of Fundamental Research
Progress in Error-Correction: New Codes for Old Noise Models
STCS Colloquium
Speaker:
Venkatesan Guruswami (Carnegie Mellon University
Department of Computer Science
5000 Forbes Avenue
Pittsburgh, PA 15213
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 24 Jan 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
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 that underlie several advances in theoretical computer science. The central challenge in coding theory is to construct codes with minimum possible redundancy for different noise 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 70 years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions routinely emerge to address the demands of modern technologies and applications in complexity theory/cryptography. This talk will survey some of our recent works on error-correction in various noise 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.
| Speaker: | Venkatesan Guruswami (Carnegie Mellon University Department of Computer Science 5000 Forbes Avenue Pittsburgh, PA 15213 United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 24 Jan 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
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 that underlie several advances in theoretical computer science. The central challenge in coding theory is to construct codes with minimum possible redundancy for different noise 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 70 years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions routinely emerge to address the demands of modern technologies and applications in complexity theory/cryptography. This talk will survey some of our recent works on error-correction in various noise 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.
- 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.