Lecture: Friday, 1pm-3pm
Instructor: Prasad Raghavendra
Office hours: Wednesday 11:00-12:00pm
Constraint satisfaction problems (CSP) are perhaps the most extensively studied family of problems in theoretical computer science. Deep and comprehensive theories have emerged around answering the following questions concerning constraint satisfaction problems:
Given a CSP instance, when is it possible to find a satisfying assignment in polynomial time, and when is it NP-complete?
(CSP Dichotomy Theorem)
Given a CSP instance that may not be completely satisfiable, how well can we approximate the optimal solution? what are the optimal approximation algorithms?
(PCP Theorem, Semidefinite programming, Unique Games Conjecture)
Yet, several new settings for CSPs and fundamental avenues for inquiry still remain open. For example,
Planted/Bayesian CSPs: What are the fundamental limits of signal-to-noise ratio at which one can recover assignments in planted CSPs.
Satisfiable CSPs: How well can one approximate CSPs under the guarantee that they are fully satisfiable?
Promise CSPs: How well can we efficiently approximate relaxed constraints, if the instance is guaranteed to satisfy all the constraints? For example, how many colors do we need to efficiently color a 3-colorable graph?
Thresholds of satisfiability: Do all random CSPs exhibit a sharp transition from satisfiability to unsatisfiability at at particular density of clauses?
In this course, we will try to survey the above topics. A tentative list of topics include the following:
Polymorphisms, CSP Dichotomy theorem.
Dinur's proof of the PCP Theorem.
Hastad's 3-query PCP.
SDP based approximation of CSPs.
Unique Games conjecture.
2-to-2 games.
Planted CSPs and Kesten-Stigum threshold.
k-SAT conjecture.
The class is aimed at graduate students specializing in theoretical computer science,statistics or related areas. A solid background in probability and linear algebra is an absolute must.
Scribing: one or two lectures 60%
Class participation 40%