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-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization

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

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

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots

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

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

Point-hyperplane Incidence Geometry and the Log-rank Conjecture

点超平面重合几何与对数秩猜想

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

Low-degree testing over grids

网格上的低度测试

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

Is This Correct? Let's Check!

它是否正确？

• 发表时间: 2023-01
• 期刊: {ITCS} 2023
• 作者: Ben;Mikulincer, Dan;Mossel, Elchanan;Sudan, Madhu
• 通讯作者: Sudan, Madhu