Award Abstract # 2006589
AF: CIF: Small: Communication complexity techniques beyond classical information theory

NSF Org: CCF
Division of Computing and Communication Foundations
Recipient: TRUSTEES OF DARTMOUTH COLLEGE
Initial Amendment Date: June 24, 2020
Latest Amendment Date: June 24, 2020
Award Number: 2006589
Award Instrument: Standard 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: October 1, 2020
End Date: September 30, 2024 (Estimated)
Total Intended Award Amount: $497,639.00
Total Awarded Amount to Date: $497,639.00
Funds Obligated to Date: FY 2020 = $497,639.00
History of Investigator:
  • Amit Chakrabarti (Principal Investigator)
    Amit.Chakrabarti@Dartmouth.edu
Recipient Sponsored Research Office: Dartmouth College
7 LEBANON ST
HANOVER
NH  US  03755-2170
(603)646-3007
Sponsor Congressional District: 02
Primary Place of Performance: Dartmouth College
Office of Sponsored Projects
Hanover
NH  US  03755-1404
Primary Place of Performance
Congressional District:
02
Unique Entity Identifier (UEI): EB8ASJBCFER9
Parent UEI: T4MWFG59C6R3
NSF Program(s): Comm & Information Foundations
Primary Program Source: 01002021DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7923, 7927, 7935, 9150
Program Element Code(s): 779700
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

Communication is central to modern computing systems, which involve data distributed across multiple entities. Developing communication-efficient algorithmic strategies (protocols) to solve problems featuring distributed data is therefore an important practical goal. Correspondingly, communication complexity---which studies the possibilities and limitations of such protocols---is important to foundational research in computer science. In fact, the influence of communication complexity runs much deeper, because the operation of an algorithm can itself be seen as a careful orchestration of information flow from input bits to output bits, which gives rise to a communication protocol between abstract entities. Key questions in communication complexity are: how much efficiency is gained by allowing the communicating parties to (a) use randomized strategies that may err with some small probability, or (b) use a complex pattern of interactive communication as opposed to a simple one? This project will address some such questions, seeking theorems that provably require fresh mathematical ideas, forcing an expansion of our mathematical arsenal. The project aims to grow the foundations of communication complexity either through novel lower bounds or by obtaining surprising new protocols that may teach us algorithmic lessons.

Viewing communication as information flow and quantifying this using the machinery of Shannon entropy and Kullback-Leibler divergence is a powerful technique for proving lower bounds on the communication required to accomplish a task. This project's central goal is to make progress on problems where this general paradigm provably cannot work. The investigator has identified some concrete communication tasks where a deterministic solution plausibly requires considerably more resources than a randomized solution, and proposes to prove such separations by developing a more delicate quantification of information flow that is attuned to deterministic communication protocols. Additionally, the project will study a class of communication problems involving parties with asymmetric knowledge (the so-called Arthur-Merlin setting, where one super-player knows all of the distributed input but is not blindly trusted by the other, regular, players), where classical information theory fails to capture the communication from the super-player.

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.

Assadi, Sepehr and Chakrabarti, Amit and Ghosh, Prantar and Stoeckl, Manuel "Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms" PODS 2023 , v.2023 , 2023 https://doi.org/10.1145/3584372.3588681 Citation Details
Chakrabarti, Amit and Ghosh, Prantar and Stoeckl, Manuel "Adversarially Robust Coloring for Graph Streams" Leibniz international proceedings in informatics , v.215 , 2022 Citation Details
Chakrabarti, Amit and McGregor, Andrew and Wirth, Anthony "Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams" , v.308 , 2024 https://doi.org/10.4230/LIPICS.ESA.2024.40 Citation Details
Chakrabarti, Amit and Stoeckl, Manuel "Finding Missing Items Requires Strong Forms of Randomness" , v.300 , 2024 https://doi.org/10.4230/LIPICS.CCC.2024.28 Citation Details
Ghosh, Prantar and Stoeckl, Manuel "Low-Memory Algorithms for Online Edge Coloring" , v.297 , 2024 https://doi.org/10.4230/LIPIcs.ICALP.2024.71 Citation Details
Stoeckl, Manuel "Streaming algorithms for the missing item finding problem" SODA 2023 , v.2023 , 2023 Citation Details

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 research project sought to quantify the communication or space resources required for solving basic algorithmic problems involving large amounts of input data spread across two or more "players" working cooperatively. Such problems arise when proving mathematical theorems about the inherent limitations of many aspects of computing. In this project, the most important aspect was to understand streaming computation, which calls for processing a continuous flow of information. Imagine trying to make sense of a fast-moving river of information where decisions need to be made quickly based on what arrives, without the luxury of pausing to sort through everything.


During this project, the PI and his collaborators established several hardness results related to these problems. Additionally, the PI and collaborators designed new and more efficient algorithms for certain data streaming challenges. A key highlight of the project was the development of a well-rounded theory for streaming algorithms that function effectively despite adversarial feedback-loop effects caused by outputs influencing future inputs processed by the same algorithm. This theory provides insights into both the possibilities and limitations in the realm of data streaming and distributed computing, based on results published throughout the project.

In addition to advancing research, this project played a crucial role in establishing a new course at Dartmouth focused on Information Theory for Computer Science. Given that Dartmouth does not have a traditional electrical engineering department, this course fills an important gap, providing students with essential knowledge and skills in this vital area of study. By equipping the next generation of computer scientists with knowledge rooted in advanced research, this initiative will help shape the future of computing and its diverse applications.


Last Modified: 12/06/2024
Modified by: Amit Chakrabarti

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page