AF: Small: New Frontiers in Local Error-Correction

点击翻译按钮获取中文摘要

Modern communication and data storage technologies use mathematical error-correcting codes to cope with noise and unreliability of physical devices. This project will develop new error-correcting codes which support "local" algorithms for error-detection and error-correction: these give strong error-correction guarantees at ultra-fast speeds. The error-correcting codes and algorithms developed in this project will have the potential be applied to real-world data storage applications, which is very relevant to current cloud computing technology. The educational component of this project will involve the mentoring and education of junior researchers who intend to pursue their own careers in research, including women and minorities. This project will also develop courses about the important advances in the relevant topics, and make the course materials publicly available.At the technical level, this project investigates the main problems on the existence and construction of, and algorithms and fundamental limits for local error-correcting codes. Local error-correcting codes are modern versions of error-correcting codes that support sublinear-time error detection and/or correction. They have gained increasing importance in theoretical computer science over the last few decades, both because of potential applications to communication and data storage, as well as connections to complexity theory, pseudorandomness, and cryptography. This project will develop new algebraic, probabilistic and algorithmic tools to design and reason about such codes, and local algorithms more generally. This project is motivated by several recent advances made by the investigator, such as the construction of new high rate error-correcting codes allowing, for the first time, subpolynomial-time error-correction and error-detection, and the first constructions of probabilistically checkable proofs of constant rate, checkable in sublinear time. These advances have significantly altered what is believed to be possible in this domain, and have the potential to dramatically change the way data is stored in data centers.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.