AF: Small: Streaming Complexity of Constraint Satisfaction Problems

AF：小：约束满足问题的流复杂性

• 批准号: 2152413
• 负责人: Madhu Sudan
• 金额: $ 50万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2152413&HistoricalAwards=false
• 关键词: AF; Small; Streaming; Complexity; Constraint

A large part of modern computation involves massive streams of data that need to be analyzed by tiny processors that are incapable of much computation or storing much information as it whizzes by. Streaming-algorithms research tackles this challenge head on and aims to come up with novel algorithms that manage to extract some global features of the data despite the limited time and memory. While many surprising tasks are by now known to be solved by streaming algorithms, and others are known to require large memory, this area still lacks broad understanding. This project aims for a systematic study of the power of streaming algorithms in the context of constraint-satisfaction problems (CSPs). CSPs are a broad, natural class of optimization problems that have been intensely explored in the context of fast algorithms without memory constraints. In that context they have served as a valuable tool in understanding the diversity of algorithms, inherent limits on algorithmic performance, and in understanding which algorithm to use for a newly discovered task. This project aims for a similar understanding of the power of streaming algorithms when memory is limited. Success in such a project would vastly improve understanding of the power, the limits, and the variety that exists among algorithms that analyze massive streams of data with limited computational resources. Such an understanding would yield a readily applicable toolkit for an application designer aiming to design a streaming algorithm for a newly encountered task, thereby vastly improving the bridge from the theory to its application. Technically this project aims for a complete classification of all constraint-satisfaction problems in the setting of streaming algorithms. Constraint-satisfaction problems form an infinite class of optimization problems where the goal is to find an assignment to n variables that maximizes the number of satisfied constraints, where a single constraint depends on a constant number of variables and restricts the joint assignment of these variables. The sets of restricted assignments defines the problem. The goal of the classification is to determine the exact approximability of the optimum for every constraint-satisfaction problem, when restricted to subpolynomial space in n, and to sublinear space in n. Additional goals involve understanding the limits of multipass algorithms. Some concrete algorithms that the project explores are "sketching algorithms," "snapshot algorithms," and "random-walk algorithms". The former two are known to exhibit surprising power. The latter classes of algorithms are broader but have not been shown to be more powerful. The ultimate goal of this project is to resolve the strength of these algorithms. On the lower-bound side, the project will explore new questions and models in communication complexity and new tools in information theory with the aim of proving limits to these algorithms. The educational component of the project involves developing courses in information theory, and including modules related to streaming algorithms in the undergraduate curriculum. Progress from the project will be reported on public domain sites like the arxiv (www.arxiv.org).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.

现代计算的很大一部分涉及大量的数据流，这些数据流需要由微型处理器进行分析，这些处理器无法进行大量计算或存储大量信息。流算法研究解决了这一挑战，旨在提出新的算法，尽管时间和内存有限，但仍能提取数据的一些全局特征。虽然现在已知许多令人惊讶的任务可以通过流算法解决，并且已知其他任务需要大量内存，但这一领域仍然缺乏广泛的理解。该项目旨在系统地研究约束满足问题（CSP）背景下的流算法的能力。CSP是一个广泛的，自然类的优化问题，已经深入探讨的快速算法的背景下，没有内存限制。在这种情况下，它们在理解算法的多样性、算法性能的固有限制以及理解将哪种算法用于新发现的任务方面充当了有价值的工具。这个项目的目的是在内存有限的情况下对流算法的能力有类似的理解。这样一个项目的成功将极大地提高人们对算法的能力、局限性和多样性的理解，这些算法可以用有限的计算资源分析大量数据流。这样的理解将产生一个易于应用的工具包，旨在为新遇到的任务设计一个流算法的应用程序设计师，从而大大提高了从理论到应用程序的桥梁。从技术上讲，这个项目的目标是在流算法的设置中对所有约束满足问题进行完整的分类。约束满足问题形成了一个无限类的优化问题，其目标是找到一个分配给n个变量，最大限度地满足约束的数量，其中一个单一的约束依赖于一个常数数量的变量，并限制这些变量的联合分配。限制赋值集定义了问题。分类的目标是确定每个约束满足问题的最优解的精确逼近性，当限制在n中的次多项式空间和n中的次线性空间时。其他目标包括理解多遍算法的局限性。该项目探索的一些具体算法是“草图算法”，“快照算法”和“随机行走算法”。前两种都表现出惊人的力量。后一类算法更广泛，但尚未显示出更强大。这个项目的最终目标是解决这些算法的强度。在下限方面，该项目将探索通信复杂性中的新问题和模型以及信息论中的新工具，目的是证明这些算法的局限性。该项目的教育部分涉及开发信息理论课程，并在本科课程中包括与流算法相关的模块。该项目的进展将在公共领域网站上报告，如arxiv（www.arxiv.org）。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

Low-degree testing over grids

网格上的低度测试

• DOI: 10.4230/lipics.approx/random.2023.41
• 发表时间: 2023
• 期刊: and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023
• 作者: Amireddy, Prashanth;Srinivasan, Srikanth;Sudan, Madhu
• 通讯作者: Sudan, Madhu

Point-hyperplane Incidence Geometry and the Log-rank Conjecture

• DOI: 10.1145/3543684
• 发表时间: 2021-01
• 期刊: ACM Transactions on Computation Theory (TOCT)
• 作者: Noah G. Singer;M. Sudan

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots

改进的流算法通过平滑快照实现最大定向剪切

• DOI: 10.1109/focs57990.2023.00055
• 发表时间: 2023
• 期刊: 64th {IEEE} Annual Symposium on Foundations of Computer Science
• 作者: Saxena, Raghuvansh R.;Singer, Noah G.;Sudan, Madhu;Velusamy, Santhoshini
• 通讯作者: Velusamy, Santhoshini

General strong polarization

• DOI: 10.1145/3188745.3188816
• 发表时间: 2018-02
• 期刊: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Jarosław Błasiok;V. Guruswami;Preetum Nakkiran;A. Rudra;M. Sudan

Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization

低深度算术电路下界：绕过集合多重线性化

• DOI: 10.4230/lipics.icalp.2023.12
• 发表时间: 2023
• 期刊: and Programming
• 作者: Amireddy, Prashanth;Garg, Ankit;Kayal, Neeraj;Saha, Chandan;Thankey, Bhargav
• 通讯作者: Thankey, Bhargav