AF: Small: Streaming Complexity of Constraint Satisfaction Problems

Harvard University, Cambridge MA

Investigators

Abstract

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.