Approximability of Constraint Satisfaction Problems in the Streaming Setting

Abstract

Maximum Constraint satisfaction problems (Max-CSPs) are ubiquitous in computer science and encompass optimization problems such as Max-CUT, Max-DICUT, Max-kSAT, Max-kAND, Max-q-Coloring, Unique Games, etc. Roughly, a Max-CSP has the following structure: there are a set of variables and a set of constraints on the variables, and the goal is to assign the variables in a way so as to maximize the number of constraints that can be satisfied. The polynomial time approximability of Max-CSPs has been the focus of intense study in the literature. More recently, there has been a lot of interest to study combinatorial optimization problems like Max-CSPs in massive data settings like the streaming setting where the input data is scanned sequentially by the algorithm and then processed in a very limited space. Prior to our work, Max-CUT was the only Max-CSP that was extensively studied in this setting. Unfortunately, these studies showed that any non-trivial streaming approximation algorithm for Max-CUT must have enough memory to store the entire input! And the question of obtaining a non-trivial approximation streaming algorithm for some Max-CSP that does not store the whole input was left wide open. The central result in this thesis gives a non-trivial polylogarithmic space streaming approximation algorithm for every Max-CSP along with a sharp dichotomy theorem showing that our algorithm is optimal among subpolynomial space ``sketching'' algorithms---a special class of streaming algorithms used widely in practice, where the algorithm's output is determined by a small sketch it produces of the input stream, and the sketch itself has the property that the sketch of the concatenation of two streams can be computed from the sketches of the two component streams. The first part of this thesis focuses on Max-DICUT which has emerged as central problem in the study of Max-CSPs in the streaming setting. The second part focuses on the dichotomy theorem and some of its consequences for Max-CSPs.