@comment{This file has been generated by Pybliographer}

@article {Tovey84,
    author = "C.A. Tovey",
    title = "A simplified {NP}-complete satisfiability problem",
    journal = "Discrete Applied Mathematics",
    Volume        = {8},
    Number        = {1},
    year = "1984",
    pages = "85--89",
eprint="elsevier:10.1016/0166-218X(84)90081-7"
}

@inproceedings{CRPhardS06,
  author = {Haviv, I. and Regev, O.},
  title = {Hardness of the Covering Radius Problem on Lattices},
  booktitle = {Proc. of 21st Ann. Conf. on Computational Complexity (CCC'06)},
  publisher = {IEEE Computer Society Press},
  year = {2006},
pages="145--158",
eprint="ccc:10.1109/CCC.2006.23"
}

@Article{GabberGa81,
title={Explicit Constructions of Linear-Sized Superconcentrators},
author={Gabber, O. and Galil, Z.},
pages={407--420},
journal=jcss,
year=1981,
month=jun,
volume=22,
number=3,
preliminary={FOCS::GabberG1979},
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib},
eprint="jcss:10.1016/0022-0000(81)90040-4"
}

@article {AlonCapalbo,
    AUTHOR = {Alon, N. and Capalbo, M.},
     TITLE = {Smaller explicit superconcentrators},
   JOURNAL = {Internet Math.},
  FJOURNAL = {Internet Mathematics},
    VOLUME = {1},
      YEAR = {2004},
    NUMBER = {2},
     PAGES = {151--163},
      ISSN = {1542-7951},
   MRCLASS = {05C75 (68R10)},
  MRNUMBER = {MR2077222 (2006a:05140)},
MRREVIEWER = {Marek Kubale},
pdf="http://www.internetmathematics.org/volumes/1/2/pp151_163.pdf",
 EPRINT    = {InternetMath:1/2/151/163},
}

@Techreport{KoLin94,
  Author        = {Ko, K.-I. and Lin, C.-L.},
  Title         = {Non-Approximability in the Polynomial-Time Hierarchy},
  Number        = {94-2},
  Institution   = {Dept. of Computer Science, SUNY at Stony Brook},
  year          = {1994}
}

@Article{PapaYanna91,
  Author        = {C. H. Papadimitriou and M. Yannakakis},
  Title         = {Optimization, approximation, and complexity classes},
  Journal       = {Journal of Computer and System Sciences},
  Volume        = 43,
  year          = 1991,
  Pages         = {425--440},
number=3,
eprint="jcss:10.1016/0022-0000(91)90023-X"
}

@article{GuruswamiMR04,
  Author        = {Guruswami, V. and Micciancio, D. and Regev, O.},
  Title         = {The Complexity of the Covering Radius Problem on Lattices and Codes},
  Journal       = {Computational Complexity},
  Volume        = {14},
  Number        = {2},
  year          = {2005},
  Pages         = {90--121},
  note          = {Preliminary version in CCC'04},
  proc_booktitle= {Proc. of 19th Ann. IEEE Conf. on Computational Complexity (CCC)},
  proc_year     = {2004},
  proc_pages    = {161--173},
  doi           = {10.1007/s00037-005-0193-y}
}

@Article {KoLin95,
  Author        = {Ko, K.-I. and Lin, C.-L.},
  Title         = {On the longest circuit in an alterable digraph},
  Journal       = {J. Global Optimization},
  Volume        = {7},
  year          = {1995},
  Number        = {3},
  Pages         = {279--295},
  issn          = {0925-5001},
  coden         = {JGOPEO},
  mrclass       = {90C35 (05C20 05C38)},
  mrnumber      = {MR1355657 (96f:90122)},
eprint="springer:k74448w88p1483ww"
}

@book {VaziraniBook,
  Author        = {Vazirani, V.V.},
  Title         = {Approximation algorithms},
  Publisher     = {Springer-Verlag},
  Address       = {Berlin},
  year          = {2001},
  Pages         = {xx+378},
  isbn          = {3-540-65367-8},
  mrclass       = {68-02 (68Q17 68Q25 68W25 90Cxx)},
  mrnumber      = {MR1851303 (2002h:68001)},
  mrreviewer    = {Mark R. Jerrum},
}

@article {LubotzkyPhSa88,
  Author        = {Lubotzky, A. and Phillips, R. and Sarnak, P.},
  Title         = {Ramanujan graphs},
  Journal       = {Combinatorica},
  Volume        = {8},
  year          = {1988},
  Number        = {3},
  Pages         = {261--277},
  issn          = {0209-9683},
  coden         = {COMBDI},
  mrclass       = {05C75 (05C25 05C50)},
  mrnumber      = {MR963118 (89m:05099)},
  mrreviewer    = {Dave Witte Morris},
eprint="springer:k285687344657q53"
}

@article {Margulis88,
  Author        = {Margulis, G. A.},
  Title         = {Explicit group-theoretic constructions of combinatorial
                    schemes and their applications in the construction of
                    expanders and concentrators},
  Journal       = {Problemy Peredachi Informatsii},
  fjournal      = {Akademiya Nauk SSSR. Institut Problem Peredachi Informatsii
                    Akademii Nauk SSSR. Problemy Peredachi Informatsii},
  Volume        = {24},
  year          = {1988},
  Number        = {1},
  Pages         = {51--60},
  issn          = {0555-2923},
  mrclass       = {68R10 (05C99 94A15)},
  mrnumber      = {MR939574 (89f:68054)},
  mrreviewer    = {Mirko K{\v{r}}iv{\'a}nek},
}

@Article{SchaeferUmans02a,
  Author         = {Schaefer, M. and Umans, C.},
  Title          = {Completeness in the Polynomial-Time Hierarchy:
                   {A} compendium},
  Journal        = {SIGACT News},
  month          = sep,
  year           = 2002,
volume=33,
number=3,
pages="32--49",
eprint="sigact:10.1145/582475.582484",
note="Guest column in Complexity Theory Column."
}

@Article{SchaeferUmans02b,
  Author         = {Schaefer, M. and Umans, C.},
  Title          = {Completeness in the Polynomial-Time Hierarchy:
                   Part {II}},
  Journal        = {SIGACT News},
  month          = dec,
  year           = 2002,
volume=33,
number=4,
pages="22--36",
eprint="sigact:10.1145/601819.601829",
note="Guest column in Complexity Theory Column."
}

@InCollection{AroraLund96,
  Author         = {Arora, S. and Lund, C.},
  Title          = {Hardness of Approximation},
  booktitle      = {Approximation algorithms for {NP}-hard problems},
  Publisher      = {PWS},
  Editor         = {Hochbaum, Dorit S.},
  Address        = {Boston},
  year           = 1996
}