Error correcting codes are a fundamental tool for protecting data in communication and storage. Since the seminal works of Shannon and Hamming in the 1950s, error correcting codes have found uses throughout computer science and engineering, including in algorithm design, complexity theory, and cryptography. The goal of this project is to develop extremely efficient decoding algorithms for error correcting codes, in a variety of settings. In addition to addressing fundamental problems in algorithmic coding theory, this research will have applications algorithm design, complexity theory and pseudorandomness. Further, this award advances education by supporting graduate students and by providing research opportunities for undergraduates. This project is an international collaboration, made possible through joint funding with the US-Israel Binational Science Foundation (BSF). The project brings together one US investigator and one Israeli investigator, both of whom are experts in algorithmic coding theory, and who have a history of successful collaboration.
This project develops linear-time and sublinear-time algorithms for decoding error correcting codes in scenarios where these codes operate at capacity: that is, where they attain the best possible combinatorial and/or information-theoretic trade-offs. The approach is to bring together algebraic, graph-theoretic, and information-theoretic techniques. Traditionally, graph-theoretic and information-theoretic techniques have been useful in developing linear-time or near-linear-time algorithms for decoding, while algebraic techniques have been useful in developing sublinear-time algorithms. By combining these techniques, this project will make progress on fundamental questions in algorithmic coding theory.
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.
