Coding theory is the study of error-correcting codes, which encode data to protect it from noise. Error-correcting codes have been studied since the 1940s; today, they are used everywhere from hard drives to satellite communication. This goal of this research is to pose and attack new fundamental questions in coding theory, inspired by new applications of coding theory across computer science, mathematics, and engineering. In answering these questions, this project not only addresses the application areas, but also develops insights to tackle long-standing open questions in coding theory. This project is interdisciplinary, and includes a synergistic education plan aimed at bringing together students from different backgrounds. The education plan incorporates course development of both graduate and undergraduate courses at Stanford University as well as training for graduate students and research opportunities for undergraduates.
In more detail, this project focuses on four new lenses into coding theory, motivated by applications in distributed storage, cryptography, algorithm design and pseudorandomness. Each of these lenses raises new fundamental questions in coding theory. These questions fall broadly into the categories of "locality" and "list-decoding." Informally, locality refers to the ability to decode a small part of the original data from only a small amount of encoded data. List-decoding refers to the setting where there is so much noise that the original data cannot be uniquely determined, and the decoder must do the best it can to narrow the possibilities to a relatively short list. By answering these new fundamental questions, this research will both make progress on the motivating applications and will also develop new theory illuminating the structure of locality and list-decoding in error correcting codes.
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.
