% haastad-khot  v001/a007 Sep 28 2005

@Article{almss,
  author =       "S. Arora and C. Lund and R. Motwani and M. Sudan and
M. Szegedy",
  title =	"Proof Verification and the Hardness of Approximation
		 Problems",
  journal =      "Journal of the {ACM}",
  volume =       "45",
  year =	 "1998",
  pages =  "501--555",
  eprint = {jacm:10.1145/278298.278306}
}

@Article{arsa,
  author =       "S. Arora and S. Safra",
  title =	"Probabilistic Checking of Proofs: {A} New
		 Characterization of {NP}",
  journal =      "Journal of the {ACM}",
  volume =       "45",
  year =	 "1998",
  pages=         "70--122",
  eprint = {jacm:10.1145/273865.273901}
}

@Article{bgs,
  author =       "M. Bellare and O. Goldreich and M. Sudan",
  title =	"Free Bits, {PCP}s, and Nonapproximability--Towards
		 Tight Results",
  journal =      "{SIAM} Journal on Computing",
  volume =       "27",
  year =	 "1998",
  pages=         "804--915",
  eprint = {sicomp:10.1137/S0097539796302531}
}

@Article{e,
  author =       "L. Engebretsen",
  title =	"The Nonapproximability of Non-Boolean Predicates",
  journal =      "{SIAM} Journal on Discrete Mathematics",
  volume =       "18",
  year =	 "2004",
  pages=         "114--129",
  eprint =       {sidma:10.1137/S0895480100380458}
}

@Article{f,
  author =       "U. Feige",
  title =	"A Threshold of $\ln n$ for Approximating Set Cover",
  journal =      "Journal of the {ACM}",
  volume =       "45",
  year =	 "1998",
  pages=         "634--652",
  eprint =       {jacm:10.1145/285055.285059}
}

@Article{fglss,
  author =       "U. Feige and S. Goldwasser and L. Lovasz and S. Safra
and
		 M. Szegedy",
  title =	"Interactive Proofs and the Hardness of Approximating
		 Cliques",
  journal =      "Journal of the {ACM}",
  volume =       "43",
  year =	 "1996",
  pages=         "268--292",
  eprint =       {jacm:10.1145/226643.226652}
}

@Article{ghs,
  author =       "V. Guruswami and J. H{\aa}stad and M. Sudan",
  title =	"Hardness of Approximate Hypergraph Coloring",
  journal =      "{SIAM} Journal on Computing",
  volume =       "31",
  year =	 "2002",
  pages=         "1663--1686",
  eprint =       {sicomp:10.1137/S0097539700377165}
}

@Inproceedings{glst,
author= "V. ~Guruswami and D. ~Levin and M. ~Sudan and L. ~Trevisan",
title = "A tight characterization of {NP} with 3 query {PCPs}",
booktitle ="Proceedings of 39th Annual {IEEE} Symposium of Foundations
of Computer Science",
year ="1998",
pages=  "8--17",
eprint = {focs:10.1109/SFCS.1998.743424}
}

@Article{h,
author="J. H\aa stad",
title="Some optimal inapproximability results",
journal="Journal of the {ACM}",
volume="48",
year="2001",
pages="798--859",
eprint = {jacm:10.1145/502090.502098}
}

@Article{hastad,
author="J. H\aa stad",
title="Clique is hard to approximate within $n^{1-\epsilon}$",
journal="Acta Mathematica",
volume=182,
year=1999,
pages="105--142",
eprint = {ActaMath:am182p01a00105}
}

@inproceedings{hk,
author="J. H{\aa}stad and S. Khot",
title="Query efficient {PCPs} with perfect completeness",
booktitle="In Proceedings of 42nd Annual {IEEE} Symposium of
Foundations of Computer Science",
year="2001",
pages="610--619",
eprint = {focs:10.1109/SFCS.2001.959937}
}

@article{hw,
author="J. H\aa stad and A. Wigderson",
title="Simple analysis of graph tests for linearity and {PCP}",
journal="Random Structures and Algorithms",
volume="22",
year="2003",
pages="139--160",
eprint = {rsa:10.1002/rsa.10068}
}

@inproceedings{kh,
author="S. Khot",
title="Improved inapproximability results for maxclique, chromatic
number and approximate graph coloring",
booktitle="Proceedings of 42nd Annual {IEEE} Symposium of 
Foundations of Computer Science",
year="2001",
pages="600--609",
eprint = {focs:10.1109/SFCS.2001.959936}
}

@inproceedings{k33,
author="S.~Khot",
title="Hardness results for coloring 3-colorable 3-uniform
hypergraphs",
booktitle="Proceedings of 43rd Annual {IEEE}
Symposium on Foundations of Computer Science",
year="2002",
pages="23--32",
eprint = {focs:10.1109/SFCS.2002.1181879}
}

@article{r,
author="R. Raz",
title="A parallel repetition theorem",
journal="{SIAM} Journal on Computing",
volume=27,
pages="763--803",
year=1998,
eprint={sicomp:10.1137/S0097539795280895},
}

@inproceedings{st,
author="A. Samorodnitsky and L. Trevisan",
title="A {PCP} characterization of {NP} with optimal amortized query
complexity",
booktitle="Proceedings of the 32nd Annual {ACM} Symposium
on Theory of Computing",
pages="191--199",
year="2000",
eprint = {stoc:10.1145/335305.335329}
}

@article{t,
author="L. Trevisan",
title="Approximating Satisfiable Satisfiability Problems",
journal="Algorithmica",
volume="28",
pages="145--172",
year="2000",
eprint = {algorithmica:j2nhr52hrjr9bp55}
}