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的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，通过评估被认为是珍贵的支持。