Congratulations to Prof. Aaron Bernstein for having the project titled "CAREER: Sublinear Graph Algorithms: New Insights for Foundation Problems" awarded by the National Science Foundation (NSF). The Award is from January 2020 to January 2025 and the total budget is $551,486. See more details at https://nsf.gov/awardsearch/showAward?AWD_ID=1942010&HistoricalAwards=false

 

The CAREER Program is an NSF-wide activity that offers the National Science Foundation's most prestigious awards in support of early-career faculty, who have the potential to serve as academic role models in research and education and to lead advances in the mission of their department or organization.

 

Project Overview:

 

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.

 

The 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.