Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:University of Memphis
  • Thomas Watson
  • (510) 437-0652
Award Date:01/16/2020
Estimated Total Award Amount: $ 427,398
Funds Obligated to Date: $ 69,417
  • FY 2020=$69,417
Start Date:10/01/2020
End Date:09/30/2025
Transaction Type:Grant
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.070
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:CAREER: Structural Communication Complexity
Federal Award ID Number:1942742
DUNS ID:055688857
Program:Algorithmic Foundations
Program Officer:
  • Joseph Maurice Rojas
  • (703) 292-8455

Awardee Location

Street:Administration 315
Awardee Cong. District:09

Primary Place of Performance

Organization Name:University of Memphis
Street:Dunn Hall, University of Memphis
Cong. District:09

Abstract at Time of Award

The field of communication complexity is about situations where two parties, call them Alice and Bob, each hold a separate piece of data, and they wish to collaboratively solve some computational problem that depends on both their inputs. How much will they need to communicate back-and-forth to achieve their goal? The field encompasses both upper bounds---i.e., the design of protocols that allow Alice and Bob to succeed using only a small amount of communication---as well as lower bounds---which show that no such efficient protocol exists for certain problems (i.e., Alice and Bob will need to communicate many bits to succeed). This serves as a natural model of distributed computing, motivated by big data and cloud computing concerns. More generally, it can be used to model any situation where flow of information between different components of a system forms a bottleneck; for this reason, communication complexity has applications to many other areas of computer science. This project will develop deep technical tools to make progress on several longstanding problems and central issues in communication complexity and its various application areas. The unifying theme of this project is the importation of insights and techniques from structural complexity, which is the area of theoretical computer science devoted to classifying problems according to their inherent computational difficulty. The education component will address the challenges of facilitating flow of ideas between theory and applications, and transitioning students from coding to problem solving to research. One specific type of tool relevant to this project is "lifting theorems", which relate communication complexity to the simpler model of query complexity. The investigator will continue to develop and apply such lifting theorems to address structural questions in communication complexity and beyond. This project will: develop fundamentally new lower bound techniques for powerful communication models, strengthen and unify classic and widely-used results, clarify the delicate relationship between communication and the amount of information Alice and Bob reveal about their inputs, advance the understanding of computational problems concerning communication complexity itself, and use structural insights to deepen the connections with circuit complexity, proof complexity, and data structures. 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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.