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

CRII：AF：最大定向切割和其他约束满足问题的流近似性

• 批准号: 2348475
• 负责人: Santhoshini Velusamy
• 金额: $ 17.5万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348475&HistoricalAwards=false
• 关键词: CRII; AF; Streaming; Approximability; Maximum

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.

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