| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | February 5, 2018 |
| Latest Amendment Date: | April 11, 2022 |
| Award Number: | 1750808 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Phillip Regalia
pregalia@nsf.gov (703)292-2981 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | February 15, 2018 |
| End Date: | January 31, 2023 (Estimated) |
| Total Intended Award Amount: | $560,000.00 |
| Total Awarded Amount to Date: | $560,000.00 |
| Funds Obligated to Date: |
FY 2019 = $348,974.00 FY 2022 = $104,599.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
5000 FORBES AVE PITTSBURGH PA US 15213-3815 (412)268-8746 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
PA US 15213-3890 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
Special Projects - CCF, Algorithmic Foundations, Comm & Information Foundations |
| Primary Program Source: |
01001920DB NSF RESEARCH & RELATED ACTIVIT 01002021DB NSF RESEARCH & RELATED ACTIVIT 01002223DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
This project aims at developing a theory and methods for correcting errors in interactive communications. Shannon's influential "A Mathematical Theory of Communication" established such a theory for one-way communications. Coding theory has subsequently produced computationally efficient methods for reliable data transmissions over unreliable channels. While error correcting codes have transformed communication technologies over the decades, modern communication settings often go beyond one-way transmissions and instead require many interleaved rounds of interactive communication. The development of interactive equivalents of good error correcting codes for such modern systems is a much harder task, which has attracted attention recently and witnessed encouraging initial successes. This project will further advance the fundamental questions underlying possibilities, limitations, and theoretical underpinnings of reliable interactive communication in the presence of noise, and thus contribute to a solid mathematical and computational theory of reliable interactive communication. The project also has a strong educational component which supports several initiatives to stimulate undergraduates, graduate students, the scientific community, and the general public through education and outreach.
The project attacks a diverse set of "classical" questions, such as determining the fundamental communication rate limits for error correction in interactive communications, and explicit constructions of tree codes, a powerful but elusive type of online code. The project also considers the broader context of interactive coding schemes and their wide ranging applicability in other areas of theoretical computer science, including cryptography, privacy, and memory efficient error resilient computations.
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.
This project advanced the theory and development of methods for correcting errors in interactive communications. Shannon's ``A Mathematical Theory of Communication'' established such a theory for one-way communications. Subsequently, coding theory produced computationally efficient methods for reliable data transmissions over unreliable channels. While error correcting codes have transformed communication technologies over the last decades modern communication settings often go beyond one-way transmissions and instead require many interleaved rounds of interactive communication. The development of interactive equivalents of good error correcting codes for such modern systems, undertaken by this project, is a much harder task. This project contributed significantly to understanding these basic and fundamental questions of what the possibilities, limitations, and theoretical underpinnings of reliable interactive communication in the presence of noise further are and contributed majorly to building a solid foundation of a mathematical and computational theory of reliable interactive communication.
The project attacked a diverse set of important aspects. This includes the most important ``classical'' questions of the research area, namely, determining the fundamental communication rate limits for error correction in interactive communications, and explicit constructions of tree-codes, a powerful but so-far elusive type of online-code. The project also considered the broader context of interactive coding schemes and their wide-ranging applicability by studying connections to other areas of theoretical computer science, including, (network) coding theory, cryptography, error resilient computations, and robust circuits.
The project had a significant broader impact, particularly educational. It supported the supervision and (partially) paid the salaries for six computer science graduate students at Carnegie Mellon University, essentially from start to finish. All six students which graduated with a PhD and four continued as tenure-track faculty at top institutions while the other two joined industrial research labs. The project enabled many undergraduate research projects. The interdisciplinary nature of the problems studied fostered collaborations between the PI and other researchers in different fields and areas. This project also supported curriculum development activities, including the creation of a new graduate level course.
Last Modified: 05/11/2023
Modified by: Bernhard Haeupler
Please report errors in award information by writing to: awardsearch@nsf.gov.
