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 ln n 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].

This file has been generated by bibtex2html 1.74