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.