AF: Medium: New Directions in Coding Theory and Pseudorandomness

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

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.