Seminar Details
Approximation Algorithms for Max-CSPs in the Streaming Model
- Start Date: March 24, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Santhoshini Velusamy - Harvard University
- Event Location: Online Event
- Event Additional Info: <p>Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p>
- Presentation Type: Stand Alone Presentation
- 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.