CRII: AF: RUI: New Frontiers in Fundamental Error-Correcting Codes

CRII：AF：RUI：基本纠错码的新领域

• 批准号: 2347371
• 负责人: Ray Li
• 金额: $ 17.43万
• 依托单位: Santa Clara University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2347371&HistoricalAwards=false
• 关键词: CRII; AF; RUI; New; Frontiers

This project studies fundamental contexts of error-correcting codes in modern applications. Error correcting codes are mathematical objects that protect information from the adverse effects of noise in a variety of computational contexts. For example, insertion/deletion-correcting codes help protect the integrity of information stored with DNA storage or magnetic storage, and quantum error-correcting codes protect the delicate entanglement of quantum states that distinguishes quantum computers from classical computers. Error correcting codes are also theoretically fundamental objects that find unexpected connections to areas like algorithms, computational complexity, and cryptography, where the applications have no apparent need for noise-resilience. Error-correcting codes have a long and rich history. Nevertheless, new demands for noise resilience and new connections to other topics in computer science and mathematics have inspired new questions and revived interest in old ones. This project considers these new and renewed questions. This project also has an educational component, which includes undergraduate research mentorship and undergraduate course development.This project tackles three fundamental questions about error-correcting codes: The first question considers codes that correct insertion and deletion errors: what are the limits of how well codes can protect information from insertions and deletions errors? This project also leverages a newly discovered algorithmic connection with insertion/deletion codes to find exceptionally fast algorithms for estimating the similarity of sequences, a central question in computational biology. The second question considers list-decodable codes, which are important in both theory and practice: what kinds of codes can achieve the theoretical optimum for list-decoding? The third question considers quantum error-correcting codes: how do physical constraints of quantum architectures limit our ability to preserve entangled quantum states?This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该项目研究现代应用中错误校正代码的基本背景。错误纠正代码是数学对象，可保护信息免受各种计算环境中噪声的不利影响。例如，插入/删除校正代码有助于保护用DNA存储或磁性存储存储的信息的完整性，而量子误差校正代码保护将量子计算机与经典计算机区分开来的量子状态的微妙纠缠。错误纠正代码也是理论上的基本对象，它们可以找到与算法，计算复杂性和加密术等领域的意外连接，在这些区域中，应用程序显然不需要噪声弹性。错误校正的代码具有悠久而丰富的历史记录。然而，对噪声弹性的新需求以及与计算机科学和数学中其他主题的新联系激发了对旧问题的新问题，并恢复了对旧问题的兴趣。该项目考虑了这些新的和更新的问题。该项目还具有一个教育组成部分，其中包括本科研究指导和本科课程的发展。该项目解决了有关错误校正代码的三个基本问题：第一个问题考虑了纠正插入和删除错误的代码：如何保护信息如何保护信息免受插入和删除的限制？该项目还利用新发现的算法连接与插入/删除代码，以找到异常快速的算法来估计序列的相似性，这是计算生物学的核心问题。第二个问题考虑了列表可解码的代码，这些代码在理论和实践中都很重要：哪些代码可以实现列表编码的理论最佳？第三个问题考虑了量子误差校正代码：量子体系结构的物​​理约束如何限制我们保留纠缠量子状态的能力？该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准通过评估来获得支持的。