AF: Small: Streaming Complexity of Constraint Satisfaction Problems

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

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.