AF: Medium: New Directions in Coding Theory and Pseudorandomness

在一些应用中，概率方法是确定各种重要对象存在性的有力工具。例如，香农的著名定理断言，随机码本可以用于在噪声信道上以最佳速率可靠地传输信息。众所周知，随机图通常是“拉姆齐”的，没有大的团或独立集，而随机稀疏图很可能是具有良好连通性的扩展器。然而，在应用程序中，重要的是显式地构造这样一个对象，并对所需的属性进行认证保证。获得与概率方法所保证的强度相当的结构通常要困难得多，而且往往是未知的。伪随机性是一个广泛的领域，它处理有效地生成对象，这些对象显示出“类随机”对象的理想属性，尽管它们是明确地或有限地随机构造的。这种伪随机结构在纠错码、复杂性理论、组合学、密码学和高维几何的研究中很重要。近年来的研究已经解决了其中的一些挑战，并导致了纠错码、扩展图、随机提取器、拉姆齐图、压缩感知矩阵等强大的结构。尽管研究这些对象的定义和动机看似不同，但这些进展大多是基于发现它们之间密切联系的见解，从而产生了丰富的理论和广泛有用的技术。尽管取得了进展，但具有最佳参数的明确结构通常仍然是开放的，并且该领域充满了由新兴应用驱动的令人兴奋的新方向。该项目将涉及一系列相互关联的研究活动，重点是纠错码和伪随机性理论。所追求的方向将包括加强各种伪随机结构之间的现有联系，并发现其新的计算应用，以及研究具有应用中经常需要的重要结构特征（如线性或稀疏性）的代码和相关对象的伪随机特性。受复杂性理论启发的编码理论主题，如列表解码和局部可测试代码，以及对诸如删除信道等难以理解的噪声模型的代码将进行研究。该项目的另一个重要目标是通过具有自然计算限制的信道编码来弥合最坏情况和概率噪声模型之间的差距。该研究将利用计算机科学的思想为编码理论的研究设定新的方向，并发现新的编码结构和解码算法，从而加强计算机科学与信息理论社区之间的联系。新的编码方案的发现在数据通信和存储方面具有潜在的直接应用。因此，许多待解决的问题除了具有基本的理论吸引力外，还具有自然的实践联系。在教育方面，该项目将吸引几名研究生，为他们提供一个刺激的研究环境，并帮助他们计划编写一本“目标导向”的编码理论教科书。

The probabilistic method is a powerful tool to establish the existenceof diverse objects of importance in several applications. For example,Shannon's famous theorem asserts that a random codebook can be usedfor reliably transmitting information at optimal rates on a noisychannel. It is well known that a random graph is typically "Ramsey"and has no large clique or independent set, and a random sparse graphis very likely to be an expander with excellent connectivity. Yet, inapplications it is important to explicitly construct such an objectwith a certified guarantee of the desired property. Obtaining suchconstructions of comparable strength to what is guaranteed by theprobabilistic method is typically much harder and often unknown.Pseudorandomness is a broad area that deals with efficientlygenerating objects that exhibit the desirable properties of"random-like" objects despite being constructed either explicitly orwith limited randomness. Such pseudorandom constructions are importantin the study of error-correcting codes, complexity theory,combinatorics, cryptography, and high-dimensional geometry. Researchin recent years has addressed some of these challenges and led topowerful constructions of error-correcting codes, expander graphs,randomness extractors, Ramsey graphs, compressed sensing matrices,etc. Despite the seemingly different definitions and motivations forthe study of these objects, much of this progress was based oninsights uncovering intimate connections between them, leading to arich theory with a common pool of broadly useful techniques.This progress notwithstanding, explicit constructions with optimalparameters typically remain open, and the area is full of exciting newdirections motivated by emerging applications. This project willinvolve a comprehensive collection of interconnected researchactivities focusing on the theory of error-correcting codes andpseudorandomness. The directions pursued will include strengtheningthe existing connections between various pseudorandom constructs anddiscovering new computational applications thereof, and investigatingthe pseudorandom properties of codes and related objects that haveimportant structural characteristics often needed in applications(such as linearity or sparsity). Topics in coding theory inspired bycomplexity theory such as list decoding and locally testable codes,and codes for poorly understood noise models such as deletion channelswill be studied. Another important goal of the project is to bridgethe gap between worst-case and probabilistic noise models via codesfor channels with natural computational restrictions.The research will use ideas from computer science in setting newdirections for research in coding theory as well as discovering newconstructions of codes and decoding algorithms, thereby enhancing theconnection between the computer science and information theorycommunities. The discovery of new coding schemes has potential directapplications in communication and storage of data. Many of thequestions to be addressed, therefore, have a natural practicalconnection alongside their fundamental theoretical appeal. On theeducation front, the project will engage several graduate students andprovide a stimulating research environment for them, and help with theplanned writing of a "goal-oriented" textbook on coding theory.