Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot
Theory of Computing, Volume 1(7), pp. 119-148, 2005
Bibliography with links to cited articles
[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 n1-ε. 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].