Clique

Probabilistic Checking of Proofs: A New Characterization of NP by Arora and Safra

Proof Verification and Hardness of Approximation Problems by ALMSS

Probabilistically Checkable Proofs and their Consequences for Approximation Algorithms by Hougardy, Promel, and Steger. They bring up the epsilon stuff that Vazarani says we don't need.

On unapproximable versions of NP-Complete Problems by Zuckerman

Robust PCP's of Proximity and Shorter PCP's PhD thesis by Prahladh Harsha

Probablistic Checking of Proofs and Hardness of Approximation Problems PhD thesis by Sanjeev Arora

Efficient Probabilistic Checkable Proofs and appliations to approximation by Bellare, Goldwasser, Lund, Russell

Interactive Proofs the hardness of approximatting cliques by Feige, Goldwasser, Lovasz, Safra, and Szegedy

Two Prove Protocols–Low Error at Affordable Rates by Feige and Kilian

Improved Non-approximabiity results by Bellare and Sudan

Clique is hard to approximate within n to the 1-ep by Hastad

Linear Degree Extractors and the Inapprox of Max Clique and Chrom Numb by Zuckerman

On the complexity of approximating the independent set problem by Berman and Schnitger

Free bits, PCPs, and non-approximability-Towards Tight Results by Bellare, Goldreich, Sudan

Approx Alg by Vazarani 2001

Dinur's Easier Proof of PCP, other papers without approx in them.

The PCP Theorem by Gap Amplification by Irit Dinur

On Dinur's Proof of the PCP theorem by Jaikumar Radhakrishnan and Madhu Sudan

Robust Characterization of Polynomials with Applications to Program Testing by Rubenfeld and Sudan

Set Cover

Two Prover One Round Proof Systems: Their Power and Their Problems by Feige and Lovasz, 1992

Efficient Probabilistic Checkable Proofs and appliations to approximation by Bellare, Goldwasser, Lund, Russell, 1993

On the Hardenss of Approximating Minimization Problems by Lund and Yannakakis, 1994

Improved low degree testing by Arora and Sudan, 1997

A Sub-Constant Error-Prob Low-Degree Test, and a Sub-Constant Error-probPCP Char of NP by Raz and Safra, 1997

A Threshold of ln n for Approximating Set Cover by Feige, 1998

Approx Alg BOOK by Vazarani 2001

Alg Construction of Sets for k-Restrictions by Alon-Moshovitz-Safra, 2006

Analytical Approach to Parallel Repition by Dinur and Steurer, 2013

The Proj Game Conj and the NP-hardness of ln n-Approx Set-Cover by Moshkovitz, 2015

VC (Vertex Cover)

Some Optimal Non-Approx results by Hastad. Inapprox for Max Cut and VC

On the hardness of approximating minimum vertex cover by Dinur and Safra

MAX3SAT

Efficient Probabilistic Checkable Proofs and appliations to approximation by Bellare, Goldwasser, Lund, Russell

Some Optimal Non-Approx results by Hastad. Inapprox for Max 3SAT

MISC

On Some Tight Inapprox Results by Berman and Karpinski. Lower bounds on approximating MAX-2SAT, E2-LIN-2, MAXCUT

LECTURE NOTES FROM WASH U

Lecture notes from Wash U