Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in TCS. 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 extremal combinatorics.
Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu.