On streaming approximation algorithms for constraint satisfaction problems

Abstract

In this thesis, we explore streaming algorithms for approximating constraint satisfaction problems (CSPs). The setup is roughly the following: A computer has limited memory space, sees a long “stream” of local constraints on a set of variables, and tries to estimate how many of the constraints may be simultaneously satisfied. The past ten years have seen a number of works in this area, and this thesis includes both expository material and novel contributions. Throughout, we emphasize connections to the broader theories of CSPs, approximability, and streaming models, and highlight interesting open problems.

The first part of our thesis is expository: We present aspects of previous works that completely characterize the approximability of specific CSPs like Max-Cut and Max-DiCut with sqrt(n)-space streaming algorithm (on n-variable instances), while characterizing the approximability of all CSPs in sqrt(n) space in the special case of “composable” (i.e., sketching) algorithms, and of a particular subclass of CSPs with linear-space streaming algorithms.

In the second part of the thesis, we present two of our own joint works. We begin with a work with Madhu Sudan and Santhoshini Velusamy in which we prove linear-space streaming approximation-resistance for all ordering CSPs (OCSPs), which “CSP-like” problems maximizing over sets of permutations. Previous works considered the maximum acyclic subgraph problem (MAS), the prototypical OCSP; even for MAS, we improve on both the inapproximability factor and the space bound. Next, we present joint work with Joanna Boyland, Michael Hwang, Tarun Prasad, and Santhoshini Velusamy in which we investigate the sqrt(n)-space streaming approximability of Boolean CSPs with negations. In particular, we give explicit sqrt(n)-space sketching approximability ratios for several families of CSPs, including Max-kAND; develop simpler optimal sketching approximation algorithms for threshold predicates; and show that previous streaming lower bounds are “incomplete” in that they fail to characterize the sqrt(n)-space streaming approximability of Max-3AND.