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

项目摘要：该项目涉及一系列集中于纠错码理论的研究和演绎活动。纠错码是用于在噪声信道上进行可靠的信息通信的组合对象。该项目集中于编码理论的渐近和算法方面，特别是旨在构建能够实现良好折衷的明确的码族以及用于编码和解码的高效算法。信道噪声通常以相反的方式建模(而不是由某种概率分布产生)，因为这将产生具有最强的差错恢复能力保证的代码和算法。将探索的中心技术概念是“列表译码”。在列表解码的情况下，解码器需要输出其编码在接收字一定距离内的所有消息。因此，人们放宽了解码器的答案始终是唯一的要求。这种放宽是必要的，以便有意义地提出解码问题，使其超越“传统”的一半距离界限，同时，即使被限制为输出一个小列表，最终也允许解码远远超出Acode的一半距离。列表译码本身是一个古老的概念(最早定义于50年代后期的S)，但直到最近才为有用的码族发现了有效的列表译码算法。因此，尽管在过去的几年里已经取得了很大的进步，但就其真正的潜力而言，列表解码仍然是一个处于初级阶段的学科。特别是，列表解码的高级概念性动机是，即使在噪声是对抗性的情况下(而不是服从假设的概率模型)，它也将使通信速率接近信道的“容量”。然而，目前还不清楚产生这种结果所需的代码。这个项目的中心目标之一是在构建这样的代码和相关的列表解码算法方面取得进展。BROAD影响：该项目将试图为研究涉及代数、组合学和概率之间罕见的相互作用的代码提供新的工具和技术。它将试图加强我们对各种嘈杂信道上可能存在的无噪声通信的基本限制的理解，并在实践中推动传输信道的使用率更接近其真正的潜力，即使面对相反的影响的错误。由于它旨在获得的结果有很大的多样性，这项研究将使从事编码理论工作的不同团体更紧密地联系在一起，并更广泛地阐述由理论计算机科学开创的基于渐近复杂性的方法的优点。在教育部分开发的课程的课堂讲稿将在网上免费提供，并最终将被修饰成关于编码理论的专著，重点放在目前标准文本所缺乏的计算复杂性上。

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.