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

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

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

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

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