Speaker:  Dor Minzer (MIT)

Title: On Approximability of Satisfiable CSPs and Friends

Abstract: Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in Theoretical Computer Science. This talk will focus on a recent line of study addressing the complexity of approximating satisfiable instances of CSPs, and connections of this study to multi-player parallel repetition theorems, property testing and combinatorics.

Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu.