Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:Rutgers University New Brunswick
  • Aaron Bernstein
  • (646) 401-3392
Award Date:01/06/2020
Estimated Total Award Amount: $ 551,846
Funds Obligated to Date: $ 49,530
  • FY 2020=$49,530
Start Date:01/15/2020
End Date:12/31/2024
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: Sublinear Graph Algorithms: New Insights for Foundational Problems
Federal Award ID Number:1942010
DUNS ID:001912864
Parent DUNS ID:001912864
Program:Algorithmic Foundations
Program Officer:
  • A. Funda Ergun
  • (703) 292-2216

Awardee Location

Street:33 Knightsbridge Road
Awardee Cong. District:06

Primary Place of Performance

Organization Name:Rutgers University New Brunswick
Cong. District:06

Abstract at Time of Award

Graphs are one of the most natural ways to represent relationships between data and are used to model a wide variety of settings: social networks, the communication infrastructure, the interconnections of financial markets, metabolic processes, and the wiring of the human brain, to name a few. Processing such graphs has long been a cornerstone of computer science research, but the rise of big data poses unique computational challenges, as the scale of the graphs in these applications has far outpaced available computing power. The goal of this project is to develop a new toolkit for processing massive graphs. This project studies a novel set of research questions in the analysis of big data, and the new tools developed can be applied to foundational optimization problems such as shortest paths and matching that are central to applications in computer science, social networks, biology, and computational economics. The focus on foundational problems allows the project to bring together undergraduate and graduate students from a wide range of backgrounds. In additional to PhD mentoring and high-school outreach, the education plan includes research opportunities for undergraduates and the development of a new course in sublinear graph algorithms at Rutgers University. This project centers on three major challenges to processing massive graphs. The first is that such graphs are too large to fit in the memory of a computer, so the data must be compressed on the fly. The second is that it would take too long for a single computer to process the graph, so the computation is distributed over many machines. The third that is that in many applications the underlying graph is changing over time and it is necessary to respond to these changes locally. The project develops novel tools for tackling each individual challenge. At the same time, the project introduces general frameworks that connect the studies of these different challenges and lead to tools that can overcome a broad set of obstacles simultaneously. More specifically, what unifies the above challenges is the need to extrapolate global information about the entire graph from local information computed in small regions. For example, can one detect overloaded vertices from a small random sample of the graph? How can shortest paths in different regions be patched together to form a path from one end of the graph to another? How can a graph be compressed to only retain the most relevant edges? By answering these and related questions, the research will help extend the motivating applications to significantly larger scales and will lead to new mathematical insights into the structure of graphs. 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.