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

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

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.