Santhoshini Velusamy, Harvard University

Abstract

A maximum constraint satisfaction problem, Max-CSP(F), is specified by a finite family of constraints F. An instance of the problem on `n’ variables is given by `m’ constraints, each applied to `k’ variables (think of `k’ as a constant), and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In this talk, I will present a non-trivial approximation algorithm for Max-CSP(F) in the single-pass streaming model. In this model, the constraints appear one by one in a stream, and the streaming algorithm must estimate the maximum number of constraints that can be satisfied using space that is only polylogarithmic in `n’ and `m’. No background in streaming algorithms or constraint satisfaction problems will be needed to enjoy this talk!

The talk will be based on thispaper and unpublished work with Chi-Ning Chou, Alexander Golovnev, and Madhu Sudan. 

A word of caution: we also talk about matching lower bounds in the paper but, just a few days ago, it was pointed out to us that there is a major bug in our proof. So, as of now, though we believe that our dichotomy theorem might still be true, our lower bound proof is flawed.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home