Approximating CSPs in the streaming setting

Speaker

Santhoshini Velusamy March 03, 2023.

Abstract

Constraint satisfaction problems (CSPs) are ubiquitous in computer science and encompass optimization problems such as Max-CUT, Max-DICUT, Max-k-SAT, Max-q-Coloring, Unique Games, etc. Until recently, Max-CUT and a few Max-2CSPs were the only CSPs studied in the streaming setting. The main focus of my talk will be the following dichotomy theorem: For every CSP, there is a constant ⍺ such that the CSP is ⍺-approximable in polylogarithmic space by a linear sketching algorithm and any sketching algorithm that beats ⍺-approximation requires polynomial space. I will also briefly discuss latest works which address some of the gaps in the above dichotomy theorem, and conclude with some interesting open problems in this area.

Based on joint works with Chi-Ning Chou, Alexander Golovnev, Raghuvansh Saxena, Madhu Sudan, Noah Singer, and Ameya Velingker that appeared in STOC, FOCS, SODA, and APPROX.