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

本项目研究纠错码在现代应用中的基本背景。纠错码是在各种计算环境中保护信息免受噪声不利影响的数学对象。例如，插入/删除纠错码有助于保护存储在DNA存储或磁存储中的信息的完整性，量子纠错码保护量子态的微妙纠缠，这是量子计算机与经典计算机的区别。从理论上讲，纠错码也是一种基本的对象，它可以在算法、计算复杂性和密码学等领域找到意想不到的联系，在这些领域，应用程序对噪声恢复能力没有明显的需求。纠错码有着悠久而丰富的历史。尽管如此，对噪声弹性的新要求以及与计算机科学和数学中其他主题的新联系激发了新的问题，并重新唤起了对旧问题的兴趣。这个项目考虑了这些新的和更新的问题。这个项目也有一个教育的组成部分，包括本科生研究指导和本科生课程开发。这个项目解决了关于纠错代码的三个基本问题：第一个问题考虑的是纠正插入和删除错误的代码：代码保护信息不受插入和删除错误影响的限度是什么？该项目还利用新发现的插入/删除代码的算法连接来寻找异常快速的算法来估计序列的相似性，这是计算生物学的一个核心问题。第二个问题考虑的是列表可解码代码，这在理论和实践中都很重要：什么样的代码可以实现列表解码的理论优化？第三个问题涉及量子纠错码：量子架构的物理约束如何限制我们保持纠缠量子态的能力？该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.