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.
(Jan 24) Introduction. CSP Dichotomy Theorem, Definition of Polymorphisms. lecture
One of original papers by Jeavons on polymorphisms link
(Jan 31) Dictatorship tests, Polymorphisms and Lack of polymorphisms implies NP-completeness.
(Feb 7) PCP Theorem: PCP Proof systems vs GapCSPs, Exponential sized PCP.
(Feb 14) Linearity testing. Wrap up proof of exponential sized PCP.
(Feb 21) Expanders and Spectral Graph Theory.
Lectures 2 and 3 in class by Guruswami and O'Donnell.
(Feb 28) A lemma on random walks expander graphs, Dinur's PCP Proof overview.
Lectures 2 and 4 in class by Guruswami and O'Donnell.
(Mar 7) Gap Amplification
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%