TCS+ talk: Wednesday, May 12 — Santhoshini Velusamy, Harvard University

by plustcs

The next TCS+ talk will take place this coming Wednesday, May 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Santhoshini Velusamy from Harvard University will speak about “Classification of the approximability of all finite Max-CSPs in the dynamic streaming setting” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Due to security concerns, registration is required to attend the interactive talk. (The recorded talk will also be posted on our website afterwards, so people who did not sign up will still be able to watch the talk)

As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

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, and this paper with Chi-Ning Chou, Alexander Golovnev, and Madhu Sudan.