CIF/AF: Small: Some fundamental complexity-inspired coding theory challenges

纠错码提供了一种明智的方法来增加数据的冗余，以便即使在被各种形式的错误破坏时也能保护其效用。代码对于数据的可靠通信和存储至关重要，并在各种应用中得到广泛使用。该项目旨在解决有关纠错码各个方面的一系列基本挑战。该项目的基本问题是由PI启发和技术集成？在复杂性理论和算法编码理论方面的工作。在这些问题上的进展将提高我们对纠错码在几种模型中的能力和局限性的理解，并加强编码理论与其他各种领域之间的联系，如信息论、组合学、伪随机性、密码学、图论和复杂性理论。例如在离散无记忆信道上的通信，其特别关注于极化码的香农容量的收敛;对最坏情况删除有弹性的码;局部可测试性和可解码性;新的编码方案的发现在数据存储和通信中具有潜在的应用。不可延展的编码方案可以用作防篡改密码学的构建块。本地可解码代码可以提高分布式存储应用的效率，从而节省大量成本。这项研究将采用计算机科学的思想，为编码理论的研究设定新的方向，从而加强计算机科学和信息理论社区之间的联系。在教育方面，该项目将吸引几名研究生，为他们提供一个激励性的研究环境，并帮助编写一本关于基本编码理论的教科书。

Error-correcting codes provide a judicious way to add redundancy to data in order to safeguard its utility even when corrupted by various forms of errors. Codes are crucial to the reliable communication and storage of data, and find widespread use in diverse applications. This project is aimed at tackling a collection of fundamental challenges concerning various aspects of error-correcting codes. The questions underlying the project are inspired and technically integrated by the PI?s ongoing work in complexity theory and algorithmic coding theory. Progress on these questions will improve our understanding of the power and limitations of error-correcting codes in several models, as well as strengthen the connections between coding theory and various other fields such as information theory, combinatorics, pseudorandomness, cryptography, graph theory, and complexity theory.The project will study the performance of error-correcting codes in many settings, such as communication on discrete memoryless channels with a specific focus on convergence to Shannon capacity of polar codes; codes resilient against worst-case deletions; local testability and decodability; non-malleability against natural tampering attacks, etc.  The discovery of new coding schemes has potential applications in data storage and communication. Non-malleable coding schemes can serve as building blocks for tamper-resilient cryptography. Locally decodable codes can improve the efficiency of distributed storage applications leading to substantial cost savings. The research will employ ideas from computer science in setting new directions for research in coding theory, thereby enhancing the connection between the computer science and information theory communities. On the education front, the project will engage several graduate students and provide a stimulating research environment for them, and help with the planned writing of a textbook on essential coding theory.