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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Type
Standard Grant (Standard)
Application #
1814629
Program Officer
Joseph Maurice Rojas
Project Start
Project End
Budget Start
2018-10-01
Budget End
2021-09-30
Support Year
Fiscal Year
2018
Total Cost
$500,000
Indirect Cost
Name
Stanford University
Department
Type
DUNS #
City
Stanford
State
CA
Country
United States
Zip Code
94305