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

Toyota Technological Institute At Chicago, Chicago IL

Investigators

Abstract

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.