AF: Small: Collaborative Research: New Challenges in Graph Stream Algorithms and Related Communication Games

许多领域的计算问题需要分析大量实体之间的交互。例如，全球社交网络中的友谊链接包含大量知识。对这些链接的详细分析可以推动社会科学研究，帮助安全分析和情报收集，并指导基础设施规划。隐藏大量信息的大型网络（用数学术语来说是图形）的其他一些重要例子是生物学中的基因和神经元网络、网页网络以及恒星和星系之间的几何和物理关系网络。此外，许多此类图随着链接的出现和消失而不断演变，可能需要重复进行昂贵的计算。在如此大的图上执行计算同时将它们完全保存在内存中通常是不可行或低效的。为了应对这一广泛的挑战，在过去十年左右的时间里，包括该项目的研究人员在内的研究人员开发了称为流式处理和草图绘制的算法技术，以更有效地对大型数据集（包括大型图形）进行计算。流算法将其输入视为有序的值序列，每个值只能读取一次。草图绘制是指使用比数据流小得多的内存来总结数据流的技术。该项目将（1）针对图问题开发新颖的流式和草图算法，这些算法足够基础，具有广泛的适用性；（2）开发此类算法的底层数学理论，以更好地理解它们的可能性和局限性。在技术层面上，该项目的一个主要目标是从上限和下限的角度攻击流式模型中的基本有向图问题：现有理论主要集中在无向图。另一个目标是深入理解随机性在解决允许有效线性草图的图形问题中的作用：这种理解目前仅限于基本统计问题。流媒体和草图算法的理论与通信复杂性密切相关，它研究解决输入分布在两个或多个站点的问题（有时称为游戏）的协议。因此，该项目将为某些此类通信游戏寻求新的协议或下限，并设计新颖的通信游戏来解决特定于图问题的流算法的各个方面。 研究人员将利用各自大学的地理邻近性，在各自的理论计算机科学研究小组之间建立更正式的联系，包括每年一次为期一天的研讨会。 他们将继续其既定的历史，开发有关该项目所包含或与该项目密切相关的研究主题的教学材料。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computational problems in many domains call for analyzing interactions among a very large number of entities. For instance, the friendship links in a globe-spanning social network contain a vast amount of knowledge. Detailed analyses of these links can drive research in the social sciences, aid security analysis and intelligence gathering, and guide infrastructure planning. Some other important examples of large networks (graphs, in mathematical parlance) that hide a wealth of information are the networks of genes and neurons in biology, the network of web pages, and the network of geometric and physical relationships between stars and galaxies. Further, many such graphs are continually evolving as links appear and disappear, potentially necessitating repeated costly computation. It is usually infeasible or inefficient to perform computations on graphs this large while holding them entirely in memory. To address this broad challenge, over the last decade or so, researchers including this project's investigators have developed algorithmic techniques known as streaming and sketching to compute more efficiently on large data sets, including large graphs. A streaming algorithm treats its input as an ordered sequence of values, each of which can be read only once. Sketching refers to techniques for summarizing a stream of data using memory much smaller than the data stream. This project will (1) develop novel streaming and sketching algorithms for graph problems that are fundamental enough to have broad applicability and (2) develop the underlying mathematical theory of such algorithms to better understand their possibilities and limitations.At a technical level, one major goal of this project is to attack basic directed graph problems in the streaming model, from both upper and lower bounds perspectives: the existing theory is mostly focused on undirected graphs. Another goal is to deeply understand the role of randomness in solving graph problems that admit efficient linear sketches: such understanding is currently limited to problems from basic statistics. The theory of streaming and sketching algorithms is closely tied to communication complexity, which studies protocols for solving problems (sometimes called games) where the input is distributed across two or more sites. Accordingly, this project will seek new protocols or lower bounds for some such communication games and design novel communication games that address aspects of streaming algorithms specific to graph problems. The investigators will leverage the geographical proximity of their respective universities to build more formal ties between their respective theoretical computer science research groups, including an annual day-long workshop. They will continue their established history of developing pedagogical materials on the research topics included in or closely related to this project.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.