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

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.