[Theory] [Theory Lunch] Santhoshini Velusamy, Wednesday, 1/16 12-1pm, JCL 390

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for theory lunch! Details
below:

***
*Date:* October 16, 2024
*Time:* 12:00pm
*Location: *JCL 390

*Title: *Streaming Approximability of Constraint Satisfaction Problems

*Speaker: *Santhoshini Velusamy

*Abstract: *Maximum Constraint satisfaction problems (Max-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. Roughly,
a Max-CSP has the following structure: there are a set of variables and a
set of constraints on the variables, and the goal is to compute the maximum
number of constraints that can be satisfied. The polynomial time
approximability of Max-CSPs has been the focus of intense study in the
literature.

More recently, there has been a lot of interest to study combinatorial
optimization problems like Max-CSPs in massive data settings like the
streaming setting where the input data is scanned sequentially by the
algorithm and then processed in a very limited space. Prior to our work,
Max-CUT was the only Max-CSP that was extensively studied in this setting.
Unfortunately, these studies showed that any non-trivial streaming
approximation algorithm for Max-CUT must have enough memory to store the
entire input! And the question of obtaining a non-trivial approximation
streaming algorithm for some Max-CSP that does not store the whole input
was left wide open.

The central result of my research is a sharp dichotomy theorem in the
dynamic setting where constraints can be added or deleted in the stream.
Namely, we give a non-trivial polylogarithmic space streaming approximation
algorithm for every Max-CSP, when one exists, and also prove that it is
optimal by showing that any streaming algorithm requires at least
exponentially more space to beat it. In my talk, I will focus on the
Max-DICUT problem which has emerged as a central problem in this study. I
will discuss in detail our dichotomy result for Max-DICUT and our more
recent results giving streaming algorithms adapted from local algorithms
for Max-DICUT with improved approximation ratios. I will also briefly touch
upon the generalizations to other Max-CSPs if time permits. I will conclude
with a discussion on interesting open problems in the area.

The talk will be based on joint works with Chi-Ning Chou, Venkatesan
Guruswami, Alexander Golovnev, Raghuvansh Saxena, Noah Singer, Madhu Sudan,
and Ameya Velingker.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241014/407924e7/attachment.html>