Santhoshini Velusamy: Approximating CSPs in the streaming setting

The class of constraint satisfaction problems (CSPs) includes but is not limited to optimization problems such as Max-CUT, Max-DICUT, Max-k-SAT, Max-q-Coloring, and Unique Games. In this talk, I will describe our recent results giving new upper and lower bounds on the approximability of every CSP in the single-pass streaming setting. In particular, for sketching algorithms, we prove the following dichotomy theorem: Any CSP is either solvable in polylogarithmic space or requires at least sqrt(n) space. We also prove stronger streaming lower bounds for some CSPs, significantly generalizing the previous works on Max-CUT. I will conclude with some interesting open problems in this direction. No background in streaming, sketching or constraint satisfaction problems will be needed to enjoy this talk!

Based on joint works with Chi-Ning Chou, Alexander Golovnev, and Madhu Sudan.