ITR: Communication in the Presence of Noise and Algorithms for Error-Correction

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

ITR: Communication in the presence of noise and Algorithms for error-correction PI: Madhu Sudan, MIT The increased reliance of information technology in our day-to-day life has resulted in an explosion in the amount of data that is stored in digital media and transmitted over the internet. Associated with the increased amount of storage are increased expectations: Over communication channels, one hopes to be able to transmit more information, faster; and on storage media one hopes to store more information, cheaply and for longer periods of time. However, all channels introduce noise over time and corrupt the stored/transmitted information. The task of coping with errors in the new information technology era leads to new challenges and a resurgence of some of the classical ones. This research project investigates foundational questions and designs solutions for some of these challenges, with special focus on the following directions: A systematic study of ``list-decoding'' algorithms as an approach to push the limits of error-correction. A worst-case approach to information theory to capture more general models of error. A reexamination of classical models of communication from a new (algorithmic/asymptotic) perspective.