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

CIF/AF：小：一些由复杂性引发的基本编码理论挑战

• 批准号: 1422045
• 负责人: Venkatesan Guruswami
• 金额: $ 49.99万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2020-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422045&HistoricalAwards=false
• 关键词: CIF; AF; Small; Some; fundamental

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.

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