Classification of the approximability of all finite Max-CSPs in the dynamic streaming setting

Abstract: A maximum constraint satisfaction problem, Max-CSP(F), is specified by a finite family of constraints F, where each constraint is of arity k. An instance of the problem on n variables is given by m applications of constraints from F to length-k subsequences of the n variables, and the goal is to find an assignment to the n variables that satisfies the maximum number of constraints. The class of Max-CSP(F) includes optimization problems such as Max-CUT, Max-DICUT, Max-3SAT, Max-q-Coloring, Unique Games, etc.

In this talk, I will present our recent dichotomy theorem on the approximability of Max-CSP(F) for every finite family F, in the single-pass dynamic streaming setting. In this setting, at each time step, a constraint is either added to or deleted from the stream. In the end, the streaming algorithm must estimate the maximum number of constraints that can be satisfied using space that is only polylogarithmic in n. No background in streaming algorithms or constraint satisfaction problems will be needed to enjoy this talk!

The talk will be based on this paper (https://eccc.weizmann.ac.il/report/2021/011/), and this paper (https://eccc.weizmann.ac.il/report/2021/063/) with Chi-Ning Chou, Alexander Golovnev, and Madhu Sudan.

computational complexitycomputational geometrycryptography and securitydiscrete mathematicsdata structures and algorithmsgame theorymachine learningquantum computing and informationcombinatoricsinformation theoryoptimization and controlprobability

Audience: researchers in the topic

( paper )

---

TCS+

Series comments: Description: Theoretical Computer Science

People can register to a talk via our webpage sites.google.com/site/plustcs/livetalk , or subscribe to our calendar and mailing list at sites.google.com/site/plustcs/rss-feeds

---