ELC Seminar (Prof. Venkatesan Guruswami )

Time & Date	April 15 (Fri) 16:00-17:00
Place	CELC (Center for ELC), Seminar room (Rm. 404)
Speaker	Prof. Venkatesan Guruswami (Carnegie Mellon University)
Title	Progress in Error-Correction: New Codes for Old Noise Models

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 underly several modern 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, both in theory and practice, in the 65+ years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions have emerged to address the demands of modern technologies. 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 the best known codes against both a constant number and a constant fraction of deletions; – node failure in distributed storage, where we give low-bandwidth repair algorithms for the ubiquitous Reed-Solomon codes. (host:O. Watanabe, watanabe@is.titech.ac.jp)

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 underly several modern 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, both in theory and practice, in the 65+ years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions have emerged to address the demands of modern technologies. 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 the best known codes against both a constant number and a constant fraction of deletions;
– node failure in distributed storage, where we give low-bandwidth repair algorithms for the ubiquitous Reed-Solomon codes.

(host:O. Watanabe, watanabe@is.titech.ac.jp)

Posted:2016年3月14日 Category:研究活動

Menu

編集 Menu

領域関係者

ELC Seminar (Prof. Venkatesan Guruswami )