## General Information and Bulletins

## Course Summary

Many optimization problems of theoretical and practical interest are NP-complete, meaning it’s impossible to compute exact methods to these complaints in polynomial time unless of course P = NP. An all natural way to deal with this curse of NP-completeness would be to seek approximate solutions rather of exact solutions. An formula with approximation ratio C computes, for each problem instance, an answer whose price is inside a factor C from the optimum. Optimization problems exhibit an array of behavior within their approximability. It’s well-known that Bin-Packing comes with an approximation formula with ratio 1+epsilon for each epsilon . Theoretically jargon, we are saying that Bin-Packing includes a polynomial-time approximation plan (PTAS). However, it had not been known up until the early 90s whether problems like MAX-3SAT, Vertex Cover, and MAX-CUT possess a PTAS. A celebrated result known as the PCP Theorem finally demonstrated these problems don’t have any PTAS unless of course P = NP. Such results that eliminate the potential of good approximation algorithms (under complexity theoretic assumptions like P != NP) are known as inapproximability results or hardness of approximation results.

The PCP Theorem comes with an equivalent formulation from the purpose of look at proof checking. The PCP theorem claims that every NP-statement includes a probabilistically checkable proof, i.e. an evidence which may be place-checked by studying merely a constant quantity of bits in the proof. These bits are selected with a randomized process utilizing a limited quantity of randomness. The checking process always accepts a proper evidence of a proper statement and rejects any cheating evidence of the wrong statement rich in probability.

The word holographic proof may also be accustomed to highlight this selection that the cheating proof should be wrong everywhere and for that reason, could be detected with a place-check. The invention from the link between proof checking and inapproximability results is among the most enjoyable theoretical developments within the last decade. Since that time, PCPs have brought to many breakthrough leads to inapproximability theory, e.g. tight hardness recent results for Clique, MAX-3SAT, and hang Cover.

This program covers most of the inapproximability results and PCPs accustomed to prove them.

No prior understanding is going to be assumed, except the fundamental theory of NP-completeness.

Participants are anticipated to scribe notes for just one lecture, however this is optional (permit this to not put you off using the course). No assignments/exams !

## Administrative Information

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

Template latex files for scribe-notes are available here (stolen from Sanjeev Arora’s course at Princeton).

This is a tentative listing of topics, not always within the order of presentation.

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

· PCP Theorem: Dinur’s proof.

· Lengthy codes, Hastad’s 3-bit PCP, Hardness of MAX-3SAT

· Hardness of Set Cover, Nearest Vector Problem

· Hardness of Clique, FGLSS Reduction

· Hardness of Edge Disjoint Pathways

· Hardness of Shortest Vector Problem

· Hardness of Minimum Distance of Code

· Hardness of Uneven k-Center Problem

· Hardness of Hypergraph Vertex Cover

· Unique Games Conjecture and it is effects

· Integrality Ratio (for optimum-CUT, Uneven Teaspoon, Sparsest Cut. )

Lecture notes for the similar course I trained at Georgia Tech (first couple of):

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

Lecture 3 (Hardness of Set Cover)

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

Lecture 6 (Hardness of Minimum distance of code)

Lecture 7 (Hardness of Clique, FGLSS)

**Lecture notes for similar course trained by Venkatesan Guruswami and Ryan O’donnell at U. Washington are available here. Take a look at Dinur’s evidence of PCP Theorem.**

PCP literature is extensive and frequently very technical. Listed here are great places to look at.

- Luca Trevisan’s recent survey are available here .
- Survey by Sanjeev Arora and Carsten Lund (chapter inside a book). Several open problems aren’t open.
- Sanjeev’s PhD Thesis for that evidence of PCP Theorem.
- Vijay Vazirani’s book on Approximation Algorithms.
- Most papers can be found from authors’ webpages.