# CS 294 | PCP and Hardness of Approximation | Spring 06

## General Information

Lecturer: Luca Trevisan, luca@eecs, 679 Soda Hall, Tel. 642 8006

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?
• 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.

1. January 18 Introduction.
2. January 23 Statement of the PCP Theorem, relation with constraint satisfaction
3. January 25 Consequences of the PCP Theorem: edge-expanders and hardness of Vertex Cover in bounded-degree graphs
4. January 30 Hardness of Metric Steiner tree, hardness of Independent Set
5. February 1 Random walks, and more on the hardness of Independent Set
February 6 no class
6. February 8 Guest Lecture on approximation algorithms via linear programming
[Notes scribed by Robi]
7. February 13 Guest Lecture on approximation algorithms via semidefinite programming
[Notes scribed by Robi]
8. February 15 Expander graphs: edge expansion, eigenvalue gap
[Notes scribed by Alexandra]
February 20 President's day, no class
9. February 22 Expander graphs: relation between eigenvalue gap and edge expansion
[Notes scribed by Olga]
10. February 27 Expander graphs: an explicit construction using polynomials
[Notes scribed by Varsha]
11. March 1 Expander graphs: the zig-zag graph product
12. March 6 Expander graphs: random walks
[Notes scribed  by Lorenzo]
13. March 8 Proof of the PCP Theorem: overview and beginning of "amplification phase"
[Notes scribed  by Grant]
14. March 13 Proof of the PCP Theorem: amplification phase
[Notes co-scribed by Madhur, Lorenzo and Grant]
15. March 15 Proof of the PCP Theorem: amplification phase
16. March 20 Proof of the PCP Theorem: amplification phase
17. March 22 Proof of the PCP Theorem: amplification phase
March 27-31 Spring break
18. April 3 Overview of the alphabet reduction phase
19. April 5 Long code, folding, long code test
20. April 10 Fourier analysis and first part of the long code test
[
Notes scribed by Cameron]
21. April 12 Second part of the long code test
[Notes scribed by Omar]
22. April 17 Second part of the long code test, conclusion
[See notes for April 12]
23. April 19 Recap of the proof of the PCP theorem, statement of the parallel repetition theorem
[Notes scribed by Omid]
24. April 24 Hastad's 3-query verifier
[Notes scribed by Omar]
25. April 26 Hastad's 3-query verifier
[Notes scribed by Henry]
26. May 1 Applications of Hastad's 3 query verifier
[Notes scribed by Omid]
27. 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:
1. Oded Goldreich, Madhu Sudan: Locally Testable Codes and PCPs of Almost-Linear Length
[Chosen by Grant]
2. 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:
1. Jeff Kahn, Gil Kalai, Nathan Linial: The Influence of Variables on Boolean Functions
2. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar: On the Hardness of Approximating Multicut and Sparsest-Cut.
[Chosen by Costis]
3. Subhash Khot, Nisheeth K. Vishnoi: The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1
4. Subhash Khot, Oded Regev: Vertex Cover Might be Hard to Approximate to within 2-epsilon
• 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.
1. Uriel Feige: A Threshold of ln n for Approximating Set Cover
[Chosen by Omar]
2. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log* n-hard to approximate
[Chosen by Lorenzo]
3. Eran Halperin and Robert Krauthgamer : Polylogarithmic inapproximability
[Chosen by Gatis]

## references

Some survey papers: