NSF-BSF: AF: Small: Algorithms for Graph-Based Codes

Stanford University, Stanford CA

Investigators

Abstract

Error-correcting codes are a fundamental tool for protecting data in communication and storage. Graph-based codes – codes constructed and analyzed using tools from combinatorics and graph theory – are an important class of error-correcting codes. This project will develop new algorithms and techniques for graph-based codes. Such algorithms will have applications not only in communication and storage, but also in areas like algorithm design and complexity theory. This project also involves educational and outreach components, such as the development of publicly available teaching materials, including a series of YouTube lectures; and research opportunities for graduate and undergraduate students, with an emphasis on recruiting from groups underrepresented in computing. This project is an international collaboration, made possible through joint funding with the US-Israel Binational Science Foundation (BSF). In more detail, this project will develop techniques for list- and local-decoding of graph-based codes. In the standard unique decoding problem, a receiver wants to reconstruct a sender’s message exactly; in list-decoding, the receiver is allowed to produce a short list of possible messages; in local-decoding, the receiver is only responsible for a small portion of the original message. While graph-based codes are extremely well-studied for unique decoding, especially in the setting of stochastic errors, they are much less common for list-decoding or local-decoding. This project will make progress on two major open problems in coding theory, beyond graph-based codes: to achieve linear-time capacity-achieving list-decoding algorithms, and to perform local decoding with high rate and low query complexity. Moreover, progress in these areas will feed back into unique decoding, leading to uniquely decodable codes with extremely efficient decoding algorithms. 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.