<div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for theory lunch! Details below:<div><br></div><div>***</div><div><b>Date:</b> October 16, 2024</div><div><b>Time:</b> 12:00pm</div><div><b>Location: </b>JCL 390</div><div><br></div><div><b>Title: </b>Streaming Approximability of Constraint Satisfaction Problems</div><div><b><br></b></div><div><b>Speaker: </b>Santhoshini Velusamy</div><div><b><br></b></div><div><b>Abstract: </b>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.</div><br>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.<br><br>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.<br><br>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.</div>