CRII: AF: Streaming Approximability of Maximum Directed Cut and other Constraint Satisfaction Problems

约束满足问题（csp）是一个普遍存在的问题，它包含了计算机科学中各个领域研究的几个重要的优化问题。它们的一些最流行的应用包括数据集群、资源规划和芯片设计。在理论计算机科学中，一些广泛应用的算法和复杂性理论工具都起源于对csp的研究。虽然传统的csp研究假设整个输入对算法是可用的，但大数据热潮已经需要在新的计算模型中研究这些问题，这些模型非常适合处理无法完全适合算法内存的非常大的数据集。流模型就是这样一种研究得很好的计算模型，其中算法的输入是作为数据流提供的，流算法必须使用有限的内存来执行所有的计算，内存比流的大小要小得多。一个特别感兴趣的CSP是最大定向切割（Max-DICUT）问题，它已经成为流设置中CSP研究的中心问题。尽管备受关注，但关于Max-DICUT和其他csp的许多基本问题在流模型中仍未得到解答。本项目旨在解决其中的一些基础问题，并对流算法在解决csp时的能力和局限性提供重要的见解。该项目还为研究生和本科生提供了研究机会，通过一门新的高级算法课程，该课程将整合这些研究方向的主题。由此产生的研究和课程材料将向一般读者提供。在研究方向上，以往的工作大多集中在“单通道”流算法上，即算法只允许通过流一次，数据到达的顺序由恶意对手决定。虽然这在理论上是一个很好的模型，但在实践中，算法通常有额外的“帮助”。例如，它们可能被允许在输入上多次传递，或者只要求在从某个分布中提取的输入上表现良好。他们可能还可以使用量子比特或机器学习预言器来预测数据流的其余部分。在这种情况下，可能存在比最佳单次通过算法的空间效率指数更高的算法。本项目旨在为Max-DICUT和其他csp在这种更一般的设置中设计流算法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Constraint Satisfaction Problems (CSPs) are ubiquitous and encompass several important optimization problems studied in diverse areas in computer science. Some of their most popular applications include data clustering, resource planning, and chip design. In theoretical computer science, several broadly-applicable algorithmic and complexity theoretic tools have originated from the study of CSPs. While traditional research on CSPs assumes that the entire input is available to the algorithm, the big data boom has necessitated studying these problems in newer models of computation that are well-suited for processing very large datasets that cannot entirely fit in the algorithm’s memory. One such well-studied model of computation is the streaming model where the input to the algorithm is provided as a stream of data, and the streaming algorithm must perform all its computations using limited memory, much smaller than the size of the stream. A particular CSP of interest is the Maximum Directed Cut (Max-DICUT) problem, which has emerged as a central problem in the study of CSPs in the streaming setting. Despite significant attention, many fundamental questions about Max-DICUT and other CSPs remain unanswered in the streaming model. This project aims to tackle some of these foundational problems and provide significant insights into the capabilities and the limitations of streaming algorithms in solving CSPs. This project also provides research opportunities for graduate and undergraduate students through a new course in advanced algorithms that will integrate topics from these research directions. The research and course materials produced as a result will be made accessible to a general audience.In terms of research directions, most previous works focused on “single-pass” streaming algorithms, where the algorithm is allowed only one pass through the stream and the order in which the data arrives is decided by a malicious adversary. While this works as an excellent model in theory, in practice, the algorithms often have additional “help”. For example, they may be allowed multiple passes over the input or required to perform well only on inputs drawn from a certain distribution. They may also have access to quantum bits or a machine learning oracle that can predict the rest of the stream. In such scenarios, there may be algorithms that are exponentially more space efficient than the best single-pass algorithms. This project aims to design streaming algorithms for Max-DICUT and other CSPs in such more general settings.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.