Classes: Mondays and Wednesdays, 1-2:30pm, 310 Soda.
Office hours: Mondays 3-4pm
Course Requirements: scribing one or two lectures (depending on
attendance); final project.
References: the main reference for the course will be
scribed lecture notes. In addition, for each lecture I will give
a link to the original papers were the results appeared and/or
survey papers discussing the results.
About this course: a typical way to "cope" with the
intractability of NP-hard optimization problems is to design algorithms that
find solutions whose cost or value close to the optimum. In several interesting
cases, it is possible to prove that even finding good approximate solutions is
as hard as finding optimal solutions. Such "inapproximability" results
are the topic of this course. Almost all such results are proved using the PCP
Theorem (and its several variants), one of the deepest theorems in computational
complexity. We will see Irit Dinur's new proof of the PCP Theorem, how to derive
stronger variants of the PCP Theorem, and how to design reductions from PCP
Theorems to optimization problems. Typically, inapproximability results are
conditional on P!=NP, a necessary assumption since "all" combinatorial
optimization problems are tractable if P=NP. The theory described in this
course, however, also leads to unconditional results showing that certain
algorithms, or classes of algorithms, cannot achieve good approximations. Time
permitting, we will also see results that are conditional on the intractability
of "unique games," an assumption that is conjectured to be equivalent
to P!=NP. This "unique games conjecture" is now the central open
question in the area.
Tentative outline:
Statements and simple consequences of the PCP Theorem
Expander graphs
Hardness of 3SAT, Vertex Cover, Steiner Tree, TSP
Dinur's proof of the PCP Theorem Part I: error-reduction
Dinur's proof of the PCP Theorem Part II: alphabet-reduction
Fourier Analysis
Long code test
Error-reduction via parallel repetition
(Sketch of) Proof of Raz's theorem? Feige-Kilian protocol?
Hastad's 3-query protocol
Tighter hardness for 3SAT, Vertex Cover, Max Cut
Graph-test Protocol
Tight hardness for Max Clique
Hard instances for the Lovasz Theta function
Hardness of Set Cover
Unique Games Conjecture
Statement of the "majority is stablest" theorem
Conditional hardness of Min Uncut
Conditional tight hardness of Max Cut
Hard instances for semidefinite programs
classes and lecture notes
Macros for lecture notes: macros.tex contains the
macros and lecture0.tex shows how to use some
features.
April 12 Second part of the long code test
[Notes scribed by Omar]
April 17 Second part of the long code test, conclusion
[See notes for April 12]
April 19 Recap of the proof of the PCP theorem, statement of the
parallel repetition theorem
[Notes scribed by Omid]
April 24 Hastad's 3-query verifier
[Notes scribed by Omar]
April 26 Hastad's 3-query verifier
[Notes scribed by Henry]
May 1 Applications of Hastad's 3 query verifier
[Notes scribed by Omid]
May 3 Query efficient verifier
May 8 Project presentations all day
projects
If you are taking the course for credit, choose a project and prepare
a 35 minutes oral presentation. Presentations will be on Friday May 5
(place and time to be announced) and on Monday May 8.
You should time your presentation for 25 minutes, in order to leave
ample time for questions.
The topic for the project should be a major result on PCP or hardness
of approximation that we will not cover in the course. Some examples
are:
Parallel repetition. This could be a year-long project.
I recommend it only to a student interested in continuing to study
it over the summer. Here a long-term goal would be to really understand
the parallel repetition theorem and recast the proof in a different
language (possibly, coding-theoretic). For the project, the goal would
be to give an overview of the structure of the proof.
Reference: Ran Raz, A Parallel Repetition Theorem.
PCPs with short proofs. This is a topic that we have
not considered at all. It would be enough to only study the
Goldreich-Sudan result, the first of the new generation of
nearly-linear length PCPs. Alternatively, the Ben Sasson-Sudan
tester for Reed-Solomon codes and its applications.
References:
Oded Goldreich, Madhu Sudan: Locally Testable Codes and PCPs of Almost-Linear Length
[Chosen by Grant]
Eli Ben-Sasson, Madhu Sudan: Simple PCPs with Poly-log Rate and Query Complexity
Layered PCPs. This is a way of constructing good "outer verifiers"
for covering and coloring problems. The most outstanding result proved with
this technique is a k-1 hardness result for the hitting set problem with sets
of size k.
Reference: Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.
[Chosen by Cameron]
Results based on unique games. Unique games give an extremely
convenient outer verfied from which to start PCP constructions. It remains
an open question whether unique games capture NP-complete problems or other
problems whose intractability is a standard conjecture. Assuming the existence
of unique games for intractable problems, the construction of inner verifiers
is greatly simplified, but optimized constructions come with new, and difficult,
analytical problems to solve. The notion of influence of variables has
played an important role in most cases, and the KKL paper is very useful background.
The paper of Chawla et al. is an example of an important result proved using
relatively simple arguments (the proof by Khot and Vishnoi is quantitatively
preferable; the paper by Khot and Vishnoi contains as a main result an unconditional
construction. You don't need to understand the unconditional construction if you
choose that paper for the project.) The Khot-Regev paper is a bit harder to read,
but it presents another outstanding result.
References:
Jeff Kahn, Gil Kalai, Nathan Linial: The Influence of Variables on Boolean Functions
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut.
[Chosen by Costis]
Subhash Khot, Nisheeth K. Vishnoi: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1
Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-epsilon
[Chosen by Madhur]
The Dinur-Safra paper on vertex cover inspired the work on unique games,
introduced the idea of decoding the long code using influence, and was the force behind
the latest renaissance of PCP results. It is a long shot to read this paper in less
than a month. If you are interested, I would suggest to choose the Khot-Regev paper
as a project. Once you know Khot-Regev inside-out, try your luck with Dinur-Safra.
Reference: Irit Dinur, Shmuel Safra. On the Hardness of Approximating Minimum Vertex-Cover
[Chosen by Omid]
Hardness results for specific problems. In the course, we focused on PCP results,
deriving hardness of approximation results only when relatively simple reductions would suffice.
Many fundamental results, however, require sophisticated reductions. Feige's tight
hardness result for Set Cover is an example of refined elegance. There are many other
possible results to look at. The result of Chuzhoy et al., for example, is just unbelievable.
Uriel Feige: A Threshold of ln n for Approximating Set Cover
[Chosen by Omar]
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate
[Chosen by Lorenzo]
Eran Halperin and Robert Krauthgamer : Polylogarithmic inapproximability
[Chosen by Gatis]