CSCI-GA.3033-028            Spring 2020

CS Dept,   New York University

Hardness of Approximation 
PCP Theorem to 2-to-2 Games Theorem

Subhash Khot

General Information and Announcements     

Course notes towards online teaching are below.

Course Summary

A more detailed description of the topic (written over a decade ago):

Many optimization problems of theoretical and practical interest are NP-complete, meaning it is impossible to compute exact solutions to these problems in polynomial time unless P = NP. A natural way to cope with this curse of NP-completeness is to seek approximate solutions instead of exact solutions. An algorithm with approximation ratio C computes, for every problem instance, a solution whose cost is within a factor C of the optimum. Optimization problems exhibit a wide range of behavior in their approximability. It is well-known that Bin-Packing has an approximation algorithm with ratio 1+\epsilon for every \epsilon > 0. In theory jargon, we say that Bin-Packing has a polynomial-time approximation scheme (PTAS). However, it wasn't known till the early 90s whether problems like MAX-3SAT, Vertex Cover, and MAX-CUT have a PTAS. A celebrated result called the PCP Theorem finally showed that these problems have no PTAS unless P = NP. Such results that rule out the possibility of good approximation algorithms (under complexity theoretic assumptions like P != NP) are called inapproximability results or hardness of approximation results.

The PCP Theorem has an equivalent formulation from the point of view of proof checking. The PCP theorem states that every NP-statement has a probabilistically checkable proof, i.e. a proof which can be "spot-checked" by reading only a constant number of bits from the proof. These bits are selected by a randomized process using a very limited amount of randomness. The checking process always accepts a correct proof of a correct statement and rejects any cheating proof of an incorrect statement with high probability. The term "holographic proof" is sometimes used to highlight this feature that a cheating proof must be wrong everywhere and therefore, can be detected by a spot-check. The discovery of the connection between proof checking and inapproximability results is one of the most exciting theoretical developments in the last decade. Since then, PCPs have led to several breakthrough results in inapproximability theory, e.g. tight hardness results for Clique, MAX-3SAT, and Set Cover.

This course will cover many of the inapproximability results and PCPs used to prove them.

 

No prior knowledge will be assumed, except the basic theory of NP-completeness.

No exams! I might give one assignment.

Administrative Information

Lectures: Mon 7:10-9:00 (CIWW 102)

Professor: Subhash Khot – Off 416,  Ph:  212-998-4859

Template latex files for scribe-notes can be found here (stolen from Sanjeev Arora's course at Princeton).

 

 

Course progression:

I will try to cover material from the recent survey article I wrote: On the Proof of the 2-to-2 Games Conjecture This could serve as the overall outline/context for the course.

1/27, 2/3

Power-point slides for the overview talk. You can also see the talk online here.

Lecture notes here and here.

 

Online teaching notes:

3/23:  L-1  L-2  L-3

3/30   L-4  L-5

4/6     L-6  L-7

 

 

------------------------------------------------------------------------------

Everything below is from past version of the course. Some links/materials could be useful. 

Here is a tentative list of topics, not necessarily in the order of  presentation.

·         PCP Theorem:  Original proof.  Low degree testing, Linearity testing

·         PCP Theorem:  Dinur’s proof. 

·         Long codes, Hastad's 3-bit PCP, Hardness of MAX-3SAT

·         Hardness of Set Cover, Closest Vector Problem

·         Hardness of Clique, FGLSS Reduction

·         Hardness of Edge Disjoint Paths

·         Hardness of Shortest Vector Problem

·         Hardness of Minimum Distance of Code

·         Hardness of Asymmetric k-Center Problem

·         Hardness of Hypergraph Vertex Cover

·         Unique Games Conjecture and its  consequences

·         Integrality Ratio (for MAX-CUT, Asymmetric TSP, Sparsest Cut,....)

·         2-to-2 Games Theorem

 

 

----------------------------------------------------------------------------

Lecture notes for the same course I taught at Georgia Tech (first few):


Lecture 1   (Basic definitions)

Lecture 2   (Equivalence of PCP Theorem to inapproximability of MAX-3SAT) 

Lecture 3   (Hardness of Set Cover)

Lecture 4   (Hastad’s 3-bit PCP)

Lecture 5   (Hastad’s 3-bit PCP continued)

Lecture 6   (Hardness of Minimum distance of code)

Lecture 7   (Hardness of  Clique, FGLSS)

Lecture notes for similar course taught  by Venkatesan Guruswami and Ryan O’donnell at U. Washington can be found here. Check out Dinur’s proof of PCP Theorem.

References

PCP literature is extensive and often very technical. Here are good places to check out.