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

点击翻译按钮获取中文摘要

Project abstract:This project involves an integrated collection of research andeducational activities focused on the theory of error-correctingcodes. Error-correcting codes are combinatorial objects used for thepurpose of reliable communication of information over a noisychannel. The project focuses on the asymptotic and algorithmic aspectsof coding theory, and in particular aims to construct explicitfamilies of codes that achieve good trade-offs together with efficientalgorithms for encoding and decoding them. The channel noise istypically modeled adversarially (as opposed to being generated by someprobability distribution), as this will yield codes and algorithmswith the strongest possible error-resilience guarantees.The central technical notion that will be explored is that of "listdecoding". Under list decoding, the decoder is supposed to output allmessages whose encodings are within a certain distance of the receivedword. Thus one relaxes the requirement that the decoder's answeralways be unique. This relaxation is necessary to meaningfully posethe question of decoding beyond the ``traditional'' half-the-distancebound, and at the same time even when constrained to output a smalllist, ends up permitting decoding well beyond half-the-distance of acode. List decoding is itself an old notion (first defined in the late50's) but it was only recently that efficient list decodingalgorithms were discovered for useful families of codes. Consequently,though much progress has been made in the last few years, listdecoding is a subject still in its infancy in terms of its truepotential. In particular, the high level conceptual motivation forlist decoding is that it will enable communication at rates close tothe channel's ``capacity'' even when the noise is adversarial (insteadof obeying an assumed probabilistic model). The codes needed for sucha result are, however, not explicitly known currently. One of thecentral goals of this project is to make progress towards theconstruction of such codes and the associated list decodingalgorithms.BROAD IMPACTS: The project will attempt to provide new tools andtechniques for the study of codes that involve a rare interplaybetween algebra, combinatorics, and probability. It will try toenhance our understanding of the fundamental limits of noiselesscommunication possible on various noisy channels, as well as push therate of usage of transmission channels in practice much closer totheir true potential even in the face of adversarially effectederrors. Due to the great diversity in the results that it aims toobtain, the research will enable bringing the different communitiesthat work on coding theory closer together, and more widely expoundthe merits of the asymptotic complexity based approach pioneered bytheoretical computer science. Lecture notes from the offerings of thecourses developed in the educational component will be made freelyavailable on the web, and will eventually be embellished into amonograph on coding theory with a focus on computational complexitythat is currently lacking in the standard texts.