| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 18, 2018 |
| Latest Amendment Date: | May 18, 2018 |
| Award Number: | 1814629 |
| Award Instrument: | Standard Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | October 1, 2018 |
| End Date: | October 31, 2021 (Estimated) |
| Total Intended Award Amount: | $500,000.00 |
| Total Awarded Amount to Date: | $500,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
450 JANE STANFORD WAY STANFORD CA US 94305-2004 (650)723-2300 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
353 Serra Mall, Gates 468 Stanford CA US 94305-5008 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
Algorithmic Foundations, Comm & Information Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
- Extremely fast algorithms for unique and list-decoding. Unique decoding refers to the problem of uniquely recovering a message, even in the presence of bounded adversarial noise; list decoding refers to the same problem where the receiver is allowed to recover a short list of possibilities. Work supported by this project has developed codes that not only achieve the best known trade-offs between the amount of noise and the communication overhead for these problems, but also admit extremely fast (near-linear-time) algorithms for them. The approach goes via "local" algorithms, which can recover a small part of the message in sub-linear time.
- New results on the list-decodability of LDPC Codes. Work supported by this award proved that Low-Density Parity-Check (LDPC) codes -- a fundamental family of codes in both theory and practice -- achieve the best possible trade-off between noise and communication overhead for list-decoding. While this result is not in itself algorithmic, it opens the door for truly linear-time list-decoding algorithms (which is currently an open problem). Indeed, graph-based codes like LDPC codes admit linear-time algorithms for unique decoding, so a combinatorial result like this is a stepping stone to such an algorithmic result. The proof techniques are also of independent interest and have already been used in several follow-up works.
- Progress on the interplay between coding theory and algorithms/computation. Some of the work supported by this award has focused on several algorithmic applications of error correcting codes, including applications in DNA storage, machine learning and streaming algorithms.
This was an international collaboration, made possible through joint funding with the US-Israel Binational Science Foundation (BSF). The project brought together one US investigator and one Israeli investigator.
Intellectual Merit. The results discussed above are of interest to the coding theory communities in Theoretical Computer Science (TCS), Electrical Engineering (EE), and Mathematics; indeed, these results have been presented at venues in all three disciplines.
Broader Impacts. This project has technological impact beyond coding theory, due to the many applications of fast algorithms for error correcting codes; for example, some of the work supported by this award focused on applications to DNA storage and machine learning. This project has educational impact through the development of course materials on coding theory (including a lecture series publicly available on YouTube), and by funding Ph.D. students and supporting undergraduate research. Finally, while funded by this grant, the PI has engaged in several activities aimed at increasing diversity in computer science, including co-organizing a mentorship program; serving on a fellowship committee for undergraduate research; co-organizing a regular Women in Theory Forum at Stanford; and serving on the TCS Women organizing committee.
Last Modified: 04/06/2022
Modified by: Mary K Wootters
Please report errors in award information by writing to: awardsearch@nsf.gov.
