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

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

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.