@article{MR2000c:68057,
    AUTHOR = {Raz, Ran},
     TITLE = {A parallel repetition theorem},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {27},
      YEAR = {1998},
    NUMBER = {3},
     PAGES = {763--803 (electronic)},
      ISSN = {1095-7111},
   MRCLASS = {68Q15 (68Q25)},
  MRNUMBER = {2000c:68057},
}

@article{MR2003j:68057,
    AUTHOR = {Guruswami, Venkatesan and H{\aa}stad, Johan and Sudan, Madhu},
     TITLE = {Hardness of approximate hypergraph coloring},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {31},
      YEAR = {2002},
    NUMBER = {6},
     PAGES = {1663--1686 (electronic)},
      ISSN = {1095-7111},
   MRCLASS = {68Q17 (05C65 05C85 68Q15)},
  MRNUMBER = {2003j:68057},
MRREVIEWER = {J{\"o}rg Rothe},
}

@incollection{MR1715618,
    AUTHOR = {H{\aa}stad, Johan},
     TITLE = {Some optimal inapproximability results},
 BOOKTITLE = {STOC '97 (El Paso, TX)},
     PAGES = {1--10 (electronic)},
 PUBLISHER = {ACM},
   ADDRESS = {New York},
      YEAR = {1999},
   MRCLASS = {68Q25 (68Q15)},
  MRNUMBER = {1 715 618},
}

@article{MR2000j:68062,
    AUTHOR = {H{\aa}stad, Johan},
     TITLE = {Clique is hard to approximate within {$n\sp {1-\epsilon}$}},
   JOURNAL = {Acta Math.},
  FJOURNAL = {Acta Mathematica},
    VOLUME = {182},
      YEAR = {1999},
    NUMBER = {1},
     PAGES = {105--142},
      ISSN = {0001-5962},
     CODEN = {ACMAA8},
   MRCLASS = {68Q17},
  MRNUMBER = {2000j:68062},
MRREVIEWER = {Frederic Green},
}

@article{MR98i:68098,
    AUTHOR = {Arora, Sanjeev and Babai, L{\'a}szl{\'o} and Stern, Jacques
              and Sweedyk, Z.},
     TITLE = {The hardness of approximate optima in lattices, codes, and
              systems of linear equations},
      NOTE = {34th Annual Symposium on Foundations of Computer Science (Palo
              Alto, CA, 1993)},
   JOURNAL = {J. Comput. System Sci.},
  FJOURNAL = {Journal of Computer and System Sciences},
    VOLUME = {54},
      YEAR = {1997},
    NUMBER = {2, part 2},
     PAGES = {317--331},
      ISSN = {0022-0000},
     CODEN = {JCSSBM},
   MRCLASS = {68Q15 (68Q25)},
  MRNUMBER = {98i:68098},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}

@article{MR96k:68093,
    AUTHOR = {Lund, Carsten and Yannakakis, Mihalis},
     TITLE = {On the hardness of approximating minimization problems},
   JOURNAL = {J. Assoc. Comput. Mach.},
  FJOURNAL = {Journal of the Association for Computing Machinery},
    VOLUME = {41},
      YEAR = {1994},
    NUMBER = {5},
     PAGES = {960--981},
      ISSN = {0004-5411},
     CODEN = {JACOAH},
   MRCLASS = {68Q25 (05C85 68Q15 68R10)},
  MRNUMBER = {96k:68093},
}

@article{MR99d:68077b,
    AUTHOR = {Arora, Sanjeev and Lund, Carsten and Motwani, Rajeev and
              Sudan, Madhu and Szegedy, Mario},
     TITLE = {Proof verification and the hardness of approximation problems},
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {45},
      YEAR = {1998},
    NUMBER = {3},
     PAGES = {501--555},
      NOTE = {Prelim. version in FOCS'92},
      ISSN = {0004-5411},
   MRCLASS = {68Q15 (03B35 03D15 68Q25)},
  MRNUMBER = {99d:68077b},
MRREVIEWER = {Oded Goldreich},
}

@article{MR99d:68077a,
    AUTHOR = {Arora, Sanjeev and Safra, Shmuel},
     TITLE = {Probabilistic checking of proofs: a new characterization of
              {NP}},
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {45},
      YEAR = {1998},
    NUMBER = {1},
     PAGES = {70--122},
      NOTE = {Prelim. version in FOCS'92},
      ISSN = {0004-5411},
   MRCLASS = {68Q15 (03B35 03D15 68Q25)},
  MRNUMBER = {99d:68077a},
MRREVIEWER = {Oded Goldreich},
}

@article{MR97h:68037,
    AUTHOR = {Feige, Uriel and Goldwasser, Shafi and Lov{\'a}sz, Laszlo and
              Safra, Shmuel and Szegedy, Mario},
     TITLE = {Interactive proofs and the hardness of approximating cliques},
   JOURNAL = {J. ACM},
  FJOURNAL = {Journal of the ACM},
    VOLUME = {43},
      YEAR = {1996},
    NUMBER = {2},
     PAGES = {268--292},
      NOTE = {Prelim. version in FOCS'91},
      ISSN = {0004-5411},
   MRCLASS = {68Q15 (68Q10 68Q25)},
  MRNUMBER = {97h:68037},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}

@TechReport{TrevisanSurvey2004,
  author =       {Luca Trevisan},
  title =        {Inapproximability of Combinatorial Optimization Problems},
  institution =  {The Electronic Colloquium in Computational Complexity},
  year =         {2004},
  number =       {65} 
} 

@article{MR86e:94018,
    AUTHOR = {Even, Shimon and Selman, Alan L. and Yacobi, Yacov},
     TITLE = {The complexity of promise problems with applications to
              public-key cryptography},
   JOURNAL = {Inform. and Control},
  FJOURNAL = {Information and Control},
    VOLUME = {61},
      YEAR = {1984},
    NUMBER = {2},
     PAGES = {159--173},
      ISSN = {0019-9958},
     CODEN = {IFCNA4},
   MRCLASS = {94A60 (68P25)},
  MRNUMBER = {86e:94018},
MRREVIEWER = {Evangelos Kranakis},
}

@article{MR2000a:68034,
    AUTHOR = {Bellare, Mihir and Goldreich, Oded and Sudan, Madhu},
     TITLE = {Free bits, {PCP}s, and nonapproximability---towards tight
              results},
   JOURNAL = {SIAM J. Comput.},
  FJOURNAL = {SIAM Journal on Computing},
    VOLUME = {27},
      YEAR = {1998},
    NUMBER = {3},
     PAGES = {804--915 (electronic)},
      ISSN = {1095-7111},
   MRCLASS = {68Q15 (68Q17 68W25)},
  MRNUMBER = {2000a:68034},
MRREVIEWER = {Frederic Green},
}

@article{MR98m:68111,
    AUTHOR = {Bellare, Mihir and Coppersmith, Don and H{\aa}stad, Johan and
              Kiwi, Marcos and Sudan, Madhu},
     TITLE = {Linearity testing in characteristic two},
      NOTE = {Codes and complexity},
   JOURNAL = {IEEE Trans. Inform. Theory},
  FJOURNAL = {Institute of Electrical and Electronics Engineers.
              Transactions on Information Theory},
    VOLUME = {42},
      YEAR = {1996},
    NUMBER = {6, part 1},
     PAGES = {1781--1795},
      ISSN = {0018-9448},
     CODEN = {IETTAW},
   MRCLASS = {68Q25 (68Q15 90C27)},
  MRNUMBER = {98m:68111},
}

@incollection{MR1619101,
    AUTHOR = {Bellare, M. and Coppersmith, D. and H{\aa}stad, J. and Kiwi,
              M. and Sudan, M.},
     TITLE = {Linearity testing in characteristic two},
 BOOKTITLE = {36th Annual Symposium on Foundations of Computer Science
              (Milwaukee, WI, 1995)},
     PAGES = {432--441},
 PUBLISHER = {IEEE Comput. Soc. Press},
   ADDRESS = {Los Alamitos, CA},
      YEAR = {1995},
   MRCLASS = {68Q25},
  MRNUMBER = {1 619 101},
}

@incollection{MR1619100,
    AUTHOR = {Bellare, Mihir and Goldreich, Oded and Sudan, Madhu},
     TITLE = {Free bits, {PCP}s and non-approximability---towards tight
              results},
 BOOKTITLE = {36th Annual Symposium on Foundations of Computer Science
              (Milwaukee, WI, 1995)},
     PAGES = {422--431},
 PUBLISHER = {IEEE Comput. Soc. Press},
   ADDRESS = {Los Alamitos, CA},
      YEAR = {1995},
   MRCLASS = {68Q25},
  MRNUMBER = {1 619 100},
}