  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 are "CSP-like" problems maximizing over sets of permutations. 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 symmetric Boolean CSPs with negations. We give explicit
$\sqrt n$-space sketching approximability ratios for several families of CSPs,
including Max-$k$AND; develop simpler optimal sketching approximation
algorithms for threshold predicates; and show that previous lower bounds fail
to characterize the $\sqrt n$-space streaming approximability of Max-$3$AND.
