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