Chi-Ning Chou

Approximability of all finite CSPs with linear sketches

In this talk, I am going to present a recent work with Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy in which we consider the approximability of constraint satisfaction problem (CSP) in the context of sketching algorithms and give a dichotomy result. Specifically, for every constraint function family and every $\beta < \gamma$, we show that either a linear sketching algorithm solves the $(\beta,\gamma)$-approximation problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in $o(\sqrt n)$ space. In the end of the talk, I will also provide several frontier open problems about approximating CSP in the streaming models.

Talk recording is available at