The PCP Theorem

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

Improved low degree testing by Arora and Sudan

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

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

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

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

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

Approx Alg 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, 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