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在复杂性理论和算法编码理论中持续的工作启发和技术整合的。这些问题的进展将提高我们对多种模型中错误纠正代码的功能和局限性的理解，并加强编码理论与其他各个领域之间的联系，例如信息理论，组合学，伪界，密码，图形理论和复杂性。极地代码的香农容量；代码抵御最坏情况的删除；本地测试和解释性；针对自然篡改攻击等，新编码方案的非固定性具有潜在的应用程序存储和通信中的应用。不可损坏的编码方案可以用作篡改加密的基础。本地可解码的代码可以提高分布式存储应用程序的效率，从而节省大量成本。该研究将采用计算机科学的思想来为编码理论的研究设定新的方向，从而增强计算机科学与信息理论社区之间的联系。在教育方面，该项目将吸引数名研究生，并为他们提供刺激性的研究环境，并帮助计划撰写有关基本编码理论的教科书。