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.