Streaming Complexity of Constraint Satisfaction Problems

Madhu Sudan (Harvard)

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 (single-pass, often dynamic) streaming settings. In particular, when streaming algorithms are constrained to sub-polynomial space in the input length and the constraints may be inserted or removed we get a fine dichotomy: CSPs on n variables are either solvable in polylogarithmic space or require at least sqrt(n) space. We also get Omega(n) lower bounds for a broad class of CSPs. Our positive results show the broad applicability of what we call ``bias-based algorithms'', and our negative results work by abstracting and significantly generalizing previous bounds for the Maximum Cut problem. In the talk we will also describe the many obvious and non-obvious open questions and directions.  


Based on the following joint works: 

1) Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy: Approximability of all Boolean CSPs in the dynamic streaming setting. CoRR abs/2102.12351 (2021)
2) Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy: Approximability of all finite CSPs in the dynamic streaming setting. CoRR abs/2105.01161 (2021)
3) Noah Singer, Madhu Sudan, Santhoshini Velusamy: Streaming approximation resistance of every ordering CSP. CoRR abs/2105.01782 (2021)
4) Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy: Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR abs/2106.13078 (2021)
Approximability of all finite CSPs in the dynamic streaming setting. CoRR abs/2105.01161