AF: Small: Sparsity in Local Computation

AF：小：局部计算的稀疏性

• 批准号: 2006664
• 负责人: Ronitt Rubinfeld
• 金额: $ 30万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006664&HistoricalAwards=false
• 关键词: AF; Small; Sparsity; Local; Computation

Consider a setting in which inputs to and outputs from a computational problem are so large that there is not enough time to read them in their entirety. However, if a user is interested only in small parts of the output at any given time, it may be possible to provide partial answers to the user in much less time than it would take to compute the whole answer, and even, perhaps, less than the time necessary to read the whole input. Such fast algorithms that compute only the specific parts of the output needed by the user are referred to as "local computation algorithms" (LCAs). There have been many successes at designing such algorithms for a variety of problems. However, most of these successes have been for inputs that are in some sense "sparse" -- for example, for social networks in which the average number of "friends" is small, or optimization problems in which at each decision point there are few possibilities to choose from. This project aims to broaden the scope of these techniques to the more common "dense" scenario. This project will include the organization of a regular workshop "Workshop on Local Algorithms (WOLA)," as well as incorporate training for graduate students, research opportunities for undergraduates, and produce material that is incorporated into the investigator's "Sublinear Time Algorithms" course.In more detail, the goal of the proposed research is to develop new tools for designing LCAs. A main focus of this project is on techniques for designing LCAs for dense problems via sparsification techniques. One success of the field of algorithms has been to show that many computations on dense graphs can be performed by first finding a sparse graph which has approximately the same solution as the dense graph, and then solving the problem on the sparse graph. This project investigates such techniques in the setting of LCAs. Furthermore, this project studies how to do such sparsification in a local manner -- without solving the whole problem up front. For example, this project will develop fast LCAs which allow a user to determine which edges are part of a sparse approximating subgraph of the original graph. The research will mine rich sources of techniques from distributed algorithms, massively parallel computation, and sublinear algorithms. A wide range of optimization problems will be considered, including problems related to finding sparse subgraphs which capture the essential connectivity features of the input graph, coloring, and the class of problems captured by covering and packing linear programs.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.

考虑这样一种情况：计算问题的输入和输出非常大，以至于没有足够的时间来完整地阅读它们。 然而，如果用户在任何给定时间仅对输出的一小部分感兴趣，则可以在比计算整个答案所花费的时间少得多的时间内向用户提供部分答案，甚至可能比阅读整个输入所需的时间少。 这种仅计算用户所需的输出的特定部分的快速算法被称为“本地计算算法”（LCA）。 已经有许多成功的设计这样的算法的各种问题。 然而，这些成功大多数都是针对某种意义上“稀疏”的输入--例如，对于“朋友”平均数量很小的社交网络，或者在每个决策点上几乎没有选择的优化问题。 该项目旨在将这些技术的范围扩大到更常见的“密集”场景。 该项目将包括定期组织“本地算法研讨会（WOLA）”，以及为研究生提供培训，为本科生提供研究机会，并制作纳入研究员“次线性时间算法”课程的材料。更详细地说，拟议研究的目标是开发设计LCA的新工具。 该项目的主要重点是通过稀疏化技术为密集问题设计LCA的技术。 算法领域的一个成功之处是表明，稠密图上的许多计算可以通过首先找到一个稀疏图来执行，该稀疏图具有与稠密图近似相同的解，然后在稀疏图上解决问题。 本项目研究在生命周期评估中使用这种技术。 此外，该项目研究如何以局部方式进行这种稀疏化-而无需预先解决整个问题。 例如，该项目将开发快速LCA，允许用户确定哪些边是原始图的稀疏近似子图的一部分。 该研究将从分布式算法、大规模并行计算和次线性算法中挖掘丰富的技术来源。 一个广泛的优化问题将被考虑，包括相关的问题，找到稀疏子图捕捉输入图的基本连通性功能，着色，并通过覆盖和包装线性programmes.This奖项捕获的问题类反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

项目成果

On the power of adaptivity in statistical adversaries

论统计对手的适应性力量

• 发表时间: 2022
• 期刊: Conference on Learning Theory (COLT 2022
• 作者: Blanc, G.;Lange, J.;Malik, A.;Tan, L.
• 通讯作者: Tan, L.

Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

• DOI: 10.4230/lipics.approx/random.2021.55
• 发表时间: 2021-07
• 期刊: ArXiv
• 作者: Amartya Shankha Biswas;T. Eden;R. Rubinfeld

A query-optimal algorithm for finding counterfactuals

用于查找反事实的查询最优算法

• 发表时间: 2022
• 期刊: International Conference on Machine Learning (ICML 2022
• 作者: Blanc, G.;Koch, C.;Lange, J.;Tan, L.
• 通讯作者: Tan, L.

Properly learning monotone functions via local correction

通过局部校正正确学习单调函数

• DOI: 10.1109/focs54457.2022.00015
• 发表时间: 2022
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Lange, Jane;Rubinfeld, Ronitt;Vasilyan, Arsen
• 通讯作者: Vasilyan, Arsen

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

• DOI: 10.48550/arxiv.2211.03232
• 发表时间: 2022-11
• 期刊: ArXiv
• 作者: Anders Aamand;Justin Y. Chen;P. Indyk;Shyam Narayanan;R. Rubinfeld;Nicholas Schiefer;Sandeep Silwal-