[1]   S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy: Proof verification and the hardness of approximation problems. Journal of the ACM, 45:501–555, 1998. [JACM:10.1145/278298.278306].

[2]   S. Arora and S. Safra: Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45:70–122, 1998. [JACM:10.1145/273865.273901].

[3]   M. Bellare, O. Goldreich, and M. Sudan: Free bits, PCPs, and nonapproximability–towards tight results. SIAM Journal on Computing, 27:804–915, 1998. [SICOMP:10.1137/S0097539796302531].

[4]   U. Feige: A threshold of lnn for approximating set cover. Journal of the ACM, 45:634–652, 1998. [JACM:10.1145/285055.285059].

[5]   U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy: Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43:268–292, 1996. [JACM:10.1145/226643.226652].

[6]   V. Guruswami, J. Håstad, and M. Sudan: Hardness of approximate hypergraph coloring. SIAM Journal on Computing, 31:1663–1686, 2002. [SICOMP:10.1137/S0097539700377165].

[7]   V. Guruswami, D. Levin, M. Sudan, and L. Trevisan: A tight characterization of NP with 3 query PCPs. In Proceedings of 39th Annual IEEE Symposium of Foundations of Computer Science, pp. 8–17, 1998. [FOCS:10.1109/SFCS.1998.743424].

[8]   J. Håstad and S. Khot: Query efficient PCPs with perfect completeness. In In Proceedings of 42nd Annual IEEE Symposium of Foundations of Computer Science, pp. 610–619, 2001. [FOCS:10.1109/SFCS.2001.959937].

[9]   S. Khot: Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings of 42nd Annual IEEE Symposium of Foundations of Computer Science, pp. 600–609, 2001. [FOCS:10.1109/SFCS.2001.959936].

[10]   S. Khot: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 23–32, 2002. [FOCS:10.1109/SFCS.2002.1181879].

[11]   R. Raz: A parallel repetition theorem. SIAM Journal on Computing, 27:763–803, 1998. [SICOMP:10.1137/S0097539795280895].

[12]   A. Samorodnitsky and L. Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 191–199, 2000. [STOC:10.1145/335305.335329].

[13]   J. Håstad: Clique is hard to approximate within n^1-ε. Acta Mathematica, 182:105–142, 1999. [ActaMath:am182p01a00105].

[14]   J. Håstad: Some optimal inapproximability results. Journal of the ACM, 48:798–859, 2001. [JACM:10.1145/502090.502098].

[15]   J. Håstad and A. Wigderson: Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms, 22:139–160, 2003. [RSA:10.1002/rsa.10068].

[16]   L. Trevisan: Approximating satisfiable satisfiability problems. Algorithmica, 28:145–172, 2000. [Algorithmica:j2nhr52hrjr9bp55].