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.

考虑一个设置，其中计算问题的输入和输出是如此之大，以至于没有足够的时间可以整体阅读它们。 但是，如果用户仅在任何给定时间对输出的一小部分感兴趣，则可能在少于计算整个答案所需的时间内向用户提供部分答案，甚至可能少于阅读整个输入所需的时间。 这样的快速算法仅计算用户所需的输出的特定部分，称为“本地计算算法”（LCAS）。 在为各种问题设计此类算法方面取得了许多成功。 但是，这些成功中的大多数都是针对“稀疏”的输入 - 例如，对于“朋友”平均数量很小的社交网络，或者在每个决策点很少有可能选择的优化问题。 该项目旨在将这些技术的范围扩大到更常见的“密集”场景。 该项目将包括定期的研讨会“本地算法研讨会（Wola）”，并为研究生的培训纳入培训，本科生的研究机会，并制作材料，这些材料已纳入研究人员的“ Sublinearial Time Algorithms”课程。 该项目的主要重点是通过稀疏技术设计LCA的技术。 算法领域的一个成功是表明，通过首先找到与密度图大致相同的解决方案，然后在稀疏图上解决问题的稀疏图可以执行许多密集图上的计算。 该项目在LCA的环境中研究了此类技术。 此外，该项目研究了如何以当地的方式进行这种稀疏 - 而无需提前解决整个问题。 例如，该项目将开发快速LCA，允许用户确定哪些边缘是原始图的稀疏近似子图的一部分。 该研究将从分布式算法，大规模并行计算和sublinear算法中挖掘丰富的技术来源。 将考虑各种优化问题，包括与寻找稀疏子图有关的问题，这些问题捕获了输入图，着色和通过覆盖和包装线性程序捕获的问题类别的基本连接性特征。该奖项反映了NSF的法定任务，并通过评估该基金会的知识绩效和广泛的影响来评估NSF的法定任务。

项目成果

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

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.

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

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.

Triangle and Four Cycle Counting with Predictions in Graph Streams

• DOI: 10.48550/arxiv.2203.09572
• 发表时间: 2022-03
• 期刊: ArXiv
• 作者: Justin Y. Chen;T. Eden;P. Indyk;Honghao Lin;Shyam Narayanan;R. Rubinfeld;Sandeep Silwal;Tal Wagner;David P. Woodruff;Michael Zhang