In this talk we will describe some of our recent work giving new upper and lower bounds on the approximability of constraint satisfaction problems (CSPs) in the streaming and sketching settings. (Streaming algorithms process the input with small space, while sketching algorithms are restricted streaming algorithms that have additional composability requirements.) When the sketching algorithms are constrained to sub-polynomial space in the input length we get a fine dichotomy: CSPs on n variables are either solvable in polylogarithmic space or require at least sqrt(n) space. Our positive results show the broad applicability of what we call ``bias-based sketching algorithms'', and our negative results work by abstracting and significantly generalizing previous bounds for the Maximum Cut problem. We will also mention some partial extensions to streaming algorithms, linear space lower bounds, ordering CSPs.
Based on joint work with Chi-Ning Chou, Sasha Golovnev and Santhoshini Velusamy.
