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

AF：小：协作研究：图流算法和相关通信游戏的新挑战

• 批准号: 1908849
• 负责人: Andrew McGregor
• 金额: $ 25万
• 依托单位: University of Massachusetts Amherst
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1908849&HistoricalAwards=false
• 关键词: AF; Small; Collaborative; Research; New

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.

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

项目成果

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

因果图近似学习的有效干预算法

• 发表时间: 2021
• 期刊: ALT 2021
• 作者: Addanki, Raghavendra;McGregor, Andrew;Musco, Cameron
• 通讯作者: Musco, Cameron

Trace Reconstruction: Generalized and Parameterized

迹线重建：广义化和参数化

• 发表时间: 2021
• 期刊: IEEE transactions on information theory
• 影响因子: 2.5
• 作者: Krishnamurthy, Akshay;Mazumdar, Arya;McGregor, Andrew;Pal, Soumyabrata
• 通讯作者: Pal, Soumyabrata

Relaxations of Envy-Freeness Over Graphs

• DOI: 10.5555/3545946.3599032
• 发表时间: 2022-02
• 作者: Justin Payan;Rik Sengupta;V. Viswanathan

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries

通过二分独立集查询进行非自适应边缘计数和采样

• 发表时间: 2022
• 期刊: ESA 2022
• 作者: Addanki, Raghavendra;McGregor, Andrew;Musco, Cameron
• 通讯作者: Musco, Cameron

Efficient Intervention Design for Causal Discovery with Latents

• 发表时间: 2020-05
• 作者: Raghavendra Addanki;S. Kasiviswanathan;A. Mcgregor;Cameron Musco