CAREER: Graph Streaming, Communication Games, and the Quest for Optimal Algorithms

点击翻译按钮获取中文摘要

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