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.