Congratulations to Prof. Sepehr Assadi for receiving the Faculty Early Career Development (CAREER) Award from the National Science Foundation (NSF) for his project titled "CAREER: Graph Streaming, Communication Games, and the Quest for Optimal Algorithms". The award is from March 2021 to February 2026 and the total budget is $558,159.
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.
Massive graphs appear in most application domains nowadays: web-pages and hyperlinks, neurons and synapses, papers and citations, or social networks and friendship links are just a few examples. Due to the sheer size and evolving nature of these graphs, processing them via traditional algorithms is often no longer a viable option. As a result, there is a rapidly growing interest in developing algorithms that explicitly account for the restrictions of processing massive graphs. Graph streaming algorithms have been particularly successful in this regard; these are algorithms that process input graphs by making one or few passes over their edges while using a limited memory, much smaller than the input size. This project focuses on further developing the theoretical foundations of graph streaming algorithms: what graph problems can be addressed efficiently via streaming algorithms, what are the inherent limitations of streaming algorithms, and how these limitations can be mitigated through better modeling assumptions? The research directions in this project go hand-in-hand with educational initiatives such as integrating related topics in advanced courses that provide research opportunities for graduate and undergraduate students, and introducing high-school students to exciting ideas in theoretical computer science.
More specifically, the focus of this project is on understanding the powers and limitations of graph streaming algorithms for several foundational problems such as coloring, matching, reachability, shortest path, and minimum cut. These are among the most studied problems in theoretical computer science with an extremely broad range of applications. However, despite significant attention, many fundamental questions regarding these problems have remained unanswered in the streaming model. This research focuses on resolving some of these questions and moving toward determining the optimal bounds on the tradeoff between space, number of passes, and approximation ratio of graph streaming algorithms for these problems. This project plans to achieve this goal by designing and analyzing better streaming algorithms as well as using communication games as a powerful tool to prove lower bounds for these problems.
More information about the award can be found from the NSF website: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2047061