CAREER: Error-Correcting Codes --- List Decoding and Related Algorithmic Challenges

University Of Washington, Seattle WA

Investigators

Abstract

Project abstract: This project involves an integrated collection of research and educational activities focused on the theory of error-correcting codes. Error-correcting codes are combinatorial objects used for the purpose of reliable communication of information over a noisy channel. The project focuses on the asymptotic and algorithmic aspects of coding theory, and in particular aims to construct explicit families of codes that achieve good trade-offs together with efficient algorithms for encoding and decoding them. The channel noise is typically modeled adversarially (as opposed to being generated by some probability distribution), as this will yield codes and algorithms with the strongest possible error-resilience guarantees. The central technical notion that will be explored is that of "list decoding". Under list decoding, the decoder is supposed to output all messages whose encodings are within a certain distance of the received word. Thus one relaxes the requirement that the decoder's answer always be unique. This relaxation is necessary to meaningfully pose the question of decoding beyond the ``traditional'' half-the-distance bound, and at the same time even when constrained to output a small list, ends up permitting decoding well beyond half-the-distance of a code. List decoding is itself an old notion (first defined in the late 50's) but it was only recently that efficient list decoding algorithms were discovered for useful families of codes. Consequently, though much progress has been made in the last few years, list decoding is a subject still in its infancy in terms of its true potential. In particular, the high level conceptual motivation for list decoding is that it will enable communication at rates close to the channel's ``capacity'' even when the noise is adversarial (instead of obeying an assumed probabilistic model). The codes needed for such a result are, however, not explicitly known currently. One of the central goals of this project is to make progress towards the construction of such codes and the associated list decoding algorithms. BROAD IMPACTS: The project will attempt to provide new tools and techniques for the study of codes that involve a rare interplay between algebra, combinatorics, and probability. It will try to enhance our understanding of the fundamental limits of noiseless communication possible on various noisy channels, as well as push the rate of usage of transmission channels in practice much closer to their true potential even in the face of adversarially effected errors. Due to the great diversity in the results that it aims to obtain, the research will enable bringing the different communities that work on coding theory closer together, and more widely expound the merits of the asymptotic complexity based approach pioneered by theoretical computer science. Lecture notes from the offerings of the courses developed in the educational component will be made freely available on the web, and will eventually be embellished into a monograph on coding theory with a focus on computational complexity that is currently lacking in the standard texts.