% expanders

@InProceedings{TaShmaUmZu01,

  author = 	 {Amnon {Ta-S}hma and Christopher Umans and David Zuckerman},

  title = 	 {Loss-less Condensers, Unbalanced Expanders, and Extractors},

  OPTbooktitle = 	 {},

  crossref =	 {STOC33},

  OPTkey = 	 {},

  pages =	 {143--162},

  OPTyear = 	 {},

  OPTeditor = 	 {},

  OPTvolume = 	 {},

  OPTnumber = 	 {},

  OPTseries = 	 {},

  OPTaddress = 	 {},

  OPTmonth = 	 {},

  OPTorganization = {},

  OPTpublisher = {},

  OPTnote = 	 {},

  OPTannote = 	 {}

}



@Proceedings{STOC33,

title={Proceedings of the Thirty-third Annual ACM Symposium on Theory of

Computing},

booktitle={Proceedings of the Thirty-third Annual ACM Symposium on

Theory of Computing},

month={6--8 } # jul,

year=2001,

address={Crete, Greece},

c-organization={ACM},

key={ACM},

crossrefonly=1

}



@Misc{MeshulamWi01,

 author = {Roy Meshulam and Avi Wigderson},

 year = {2001},

 note = {In preparation},

}



@article {Gromov83,

    AUTHOR = {Gromov, Mikhael},

     TITLE = {Filling {R}iemannian manifolds},

   JOURNAL = {Journal of Differential Geometry},

    VOLUME = {18},

      YEAR = {1983},

    NUMBER = {1},

     PAGES = {1--147},

      ISSN = {0022-040X},

     CODEN = {JDGEAS},

   MRCLASS = {53C20 (53C21 57R99)},

  MRNUMBER = {85h:53029},

MRREVIEWER = {Yu. Burago},

}



@article {Gromov00,

    AUTHOR = {Gromov, Misha},

     TITLE = {Spaces and questions},

      NOTE = {Part I of Special Volume on GAFA 2000 (Tel Aviv, 1999)},

   JOURNAL = {Geometric and Functional Analysis},

      YEAR = {2000},

     PAGES = {118--161},

      ISSN = {1016-443X},

     CODEN = {GFANFB},

   MRCLASS = {53C23 (57-XX)},

  MRNUMBER = {1 826 251},

}



@article {KaltonRo83,

    AUTHOR = {Kalton, Nigel J. and Roberts, James W.},

     TITLE = {Uniformly exhaustive submeasures and nearly additive set

              functions},

  JOURNAL = {Transactions of the American Mathematical Society},

    VOLUME = {278},

      YEAR = {1983},

    NUMBER = {2},

     PAGES = {803--816},

      ISSN = {0002-9947},

     CODEN = {TAMTAM},

   MRCLASS = {28A60 (46A06)},

  MRNUMBER = {85f:28006},

MRREVIEWER = {Z. Lipecki},

}





@book {Lubotzky94,

    AUTHOR = {Lubotzky, Alexander},

     TITLE = {Discrete groups, expanding graphs and invariant measures},

 PUBLISHER = {Birkh\"auser Verlag},

   ADDRESS = {Basel},

      YEAR = {1994},

     PAGES = {xii+195},

      ISBN = {3-7643-5075-X},

   MRCLASS = {22E40 (05C25 11F70 28C10 43A07)},

  MRNUMBER = {96g:22018},

MRREVIEWER = {Wolfgang Woess},

}





@article {LubotzkyPa01,

    AUTHOR = {Lubotzky, Alexander and Pak, Igor},

     TITLE = {The product replacement algorithm and {K}azhdan's property

              ({T})},

  JOURNAL = {Journal of the American Mathematical Society},

    VOLUME = {14},

      YEAR = {2001},

    NUMBER = {2},

     PAGES = {347--363 (electronic)},

      ISSN = {0894-0347},

   MRCLASS = {60B15 (05C25 22D10 60J10)},

  MRNUMBER = {1 815 215},

}

@incollection {AlonLuWi01,

    AUTHOR = {Alon, Noga and Lubotzky, Alexander and Wigderson, Avi},

     TITLE = {Semi-direct product in groups and zig-zag product in graphs:

              connections and applications (extended abstract)},

 BOOKTITLE = {42nd IEEE Symposium on Foundations of Computer Science (Las

              Vegas, NV, 2001)},

     PAGES = {630--637},

 PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},

      YEAR = {2001},

   MRCLASS = {20E22 (05C25 68R10)},

  MRNUMBER = {1 948 752},

}



@Proceedings{FOCS42,

title={42nd Annual Symposium on Foundations of Computer Science},

booktitle={42nd Annual Symposium on Foundations of Computer

Science},

month={14-17 } # oct,

year=2001,

address={Las Vegas, Nevada},

organization={IEEE},

crossrefonly=1,

}



@InProceedings{ImpagliazzoShWi00,

  author =       {Russell Impagliazzo and Ronen Shaltiel and Avi Wigderson},

  title =        {Extractors and Pseudo-Random Generators with Optimal Seed Length},

  booktitle =    {Proceedings of the Thirty-Second Annual ACM Symposium on

the Theory of Computing},

  OPTcrossref =  {},

  OPTkey =       {},

  pages =     {1--10},

  year =         {2000},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Portland, Oregon},

  month =        {May},

  c-organization = {ACM},

  OPTpublisher = {},

  note =         {See also ECCC TR00-009},

  OPTannote =    {}

}







@InProceedings{Trevisan99,

  author =       {Luca Trevisan},

  title =        {Construction of Extractors using Pseudo-Random Generators},

  booktitle =    {Proceedings of the Thirty-First Annual ACM Symposium on

the Theory of Computing},

  OPTcrossref =  {},

  OPTkey =       {},

  pages =     {141--148},

  year =         {1999},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Atlanta, GA},

  month =        {May},

  c-organization = {ACM},

  OPTpublisher = {},

  note =         {See also ECCC TR98-55},

  OPTannote =    {}

}





@InProceedings{RazReVa99a,

  author =       {Ran Raz and Omer Reingold and Salil Vadhan},

  title =        {Extracting all the Randomness and Reducing the Error in

{T}revisan's Extractors},

  booktitle =    {Proceedings of the Thirty-First Annual ACM Symposium on

the Theory of Computing},

  OPTcrossref =  {},

  OPTkey =       {},

  pages =        {149--158},

  year =         {1999},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Atlanta, GA},

  OPTmonth =     {},

  OPTorganization = {},

  c-organization = {ACM} ,

  OPTpublisher = {},

  OPTnote =      {},

  OPTannote =    {}

}



@InProceedings{RazRe99,

  author =       {Ran Raz and Omer Reingold},

  title =        {On Recycling the Randomness of the States in Space Bounded

Computation},

  booktitle =    {Proceedings of the Thirty-First Annual ACM Symposium on

the Theory of Computing},

  OPTcrossref =  {},

  OPTkey =       {},

  OPTpages =     {},

  year =         {1999},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Atlanta, GA},

  month =        {May},

  c-organization = {ACM} ,

  OPTorganization = {},

  OPTpublisher = {},

  OPTnote =      {},

  OPTannote =    {}

}



@Misc{Trevisan98,

  OPTkey =       {},

  author =       {Luca Trevisan},

  title =        {Constructions of Near-Optimal Extractors Using

                  Pseudo-Random Generators},

  howpublished = {{\em Electronic Colloquium on Computational Complexity}

Technical Report TR98-55},

  year =         {1998},

  month =        {September},

  note =         {Extended abstract in these proceedings},

  OPTannote =    {}

}



@Article{NisanWi94,

title={Hardness vs Randomness},

author={Noam Nisan and Avi Wigderson},

pages={149--167},

journal=jcss,

year=1994,

month=oct,

volume=49,

number=2,

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}

}



@article {WigdersonZu99,

   AUTHOR = {Wigderson, Avi and Zuckerman, David},

    TITLE = {Expanders that beat the eigenvalue bound: explicit construction

             and applications},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal on Combinatorics and

             the Theory of Computing},

   VOLUME = {19},

     YEAR = {1999},

   NUMBER = {1},

    PAGES = {125--138},

     ISSN = {0209-9683},

  MRCLASS = {15-XX},

 MRNUMBER = {1 722 214},

}



@Article{GoldwasserMi84,

title={Probabilistic Encryption},

author={Shafi Goldwasser and Silvio Micali},

pages={270--299},

journal=jcss,

year=1984,

month=apr,

volume=28,

number=2,

preliminary={STOC::GoldwasserM1982},

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}

}



@InProceedings{Yao82,

title={Theory and Applications of Trapdoor Functions (Extended

Abstract)},

author={Yao, Andrew C.},

pages={80--91},

crossref={FOCS23},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS23,

title={23rd Annual Symposium on Foundations of Computer Science},

booktitle={23rd Annual Symposium on Foundations of Computer Science},

month={3--5 } # nov,

year=1982,

address={Chicago, Illinois},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Article{Zuckerman97,

  author =       {David Zuckerman},

  title =        {Randomness-Optimal Oblivious Sampling},

  journal =      {Random Structures \& Algorithms},

  year =         {1997},

  OPTkey =       {},

  volume =       {11},

  number =       {4},

  pages =        {345--367},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Article{GoldreichWi97,

  author =       {Oded Goldreich and Avi Wigderson},

  title =        {Tiny Families of Functions with Random Properties: A

Quality-Size Trade-off for Hashing},

  journal =      {Random Structures \& Algorithms},

  year =         {1997},

  OPTkey =       {},

  volume =       {11},

  number =       {4},

  pages =        {315--343},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@InProceedings{TaShma96,

title={On Extracting Randomness From Weak Random Sources (Extended

Abstract)},

author={Amnon {Ta-S}hma},

pages={276--285},

crossref={STOC28},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC28,

title={Proceedings of the Twenty-Eighth Annual ACM Symposium on

the Theory of Computing},

booktitle={Proceedings of the Twenty-Eighth Annual ACM Symposium on

the Theory of Computing},

month={22--24 } # may,

year=1996,

address={Philadelphia, Pennsylvania},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{TaShma98,

  author =       {Amnon {Ta-S}hma},

  title =        {Almost Optimal Dispersers},

  booktitle =    "Proceedings of the 30th Annual ACM Symposium on

                  Theory of Computing",

  year =         "1998",

  organization = "ACM",

  address =      "Dallas, TX",

  month =        "May",

  note =         {},

  pages =        "196--202"

}



@Article{Sipser88,

title={Expanders, Randomness, or Time versus Space},

author={Michael Sipser},

pages={379--383},

journal=jcss,

year=1988,

month=jun,

volume=36,

number=3,

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}

}



@Article{NisanZu96,

title={Randomness is Linear in Space},

author={Noam Nisan and David Zuckerman},

pages={43--52},

journal=jcss,

year=1996,

month=feb,

volume=52,

number=1,

preliminary={STOC::NisanZ1993},

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}

}



@string{algor={Algorithmica}}



@Article{Zuckerman96,

title={Simulating {BPP} Using a General Weak Random Source},

author={David Zuckerman},

pages={367--391},

journal=algor,

year=1996,

month=oct # "/" # nov,

volume=16,

number={4/5},

source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/misc/algor.bib}

}



@Misc{GoldreichZu97,

  OPTkey =       {},

  author =       {Oded Goldreich and David Zuckerman},

  title =        {Another proof that $\mbox{BPP}\subseteq\mbox{PH}$ (and

more)},

  howpublished = {{\em Electronic Colloquium on Computational Complexity}

Technical Report TR97-045},

  month =        {September},

  year =         {1997},

  note =         {\verb|http://www.eccc.uni-trier.de/eccc|},

  OPTannote =    {}

}



@string{lncs={Lecture Notes in Computer Science}}



@InProceedings{AndreevClRo97,

title={Worst-Case Hardness Suffices for Derandomization: A New Method

for Hardness-Randomness Trade-Offs},

author={Alexander E. Andreev and Andrea E. F. Clementi and Jos{\'e} D.

P. Rolim},

crossref={icalp97},

pages={177--187},

source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/icalp/icalp.bib}

}



@Proceedings{ICALP97,

editor={Pierpaolo Degano and Robert Gorrieri and Alberto

Marchetti-Spaccamela},

title={Automata, Languages and Programming, 24th International

Colloquium},

booktitle={Automata, Languages and Programming, 24th International

Colloquium},

address={Bologna, Italy},

month={7--11~} # jul,

year=1997,

series=lncs,

volume=1256,

publisher={Springer-Verlag},

comment={ISBN 3-540-63165-8},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/icalp/icalp.bib}

}



@Article{SanthaVa86,

title={Generating Quasi-random Sequences from Semi-random Sources},

author={Miklos Santha and Umesh V. Vazirani},

pages={75--87},

journal=jcss,

year=1986,

month=aug,

volume=33,

number=1,

preliminary={FOCS::SanthaV1984},

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}

}



@InProceedings{Vazirani87b,

title={Efficiency Considerations in Using Semi-random Sources

(Extended Abstract)},

author={Vazirani, Umesh V.},

pages={160--168},

crossref={STOC19},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC19,

title={Proceedings of the Nineteenth Annual ACM Symposium on Theory of

Computing},

booktitle={Proceedings of the Nineteenth Annual ACM Symposium on

Theory of Computing},

month={25--27 } # may,

year=1987,

address={New York City},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{VaziraniVa85,

title={Random Polynomial Time Is Equal to Slightly-random Polynomial

Time},

author={Vazirani, Umesh V. and Vazirani, Vijay V.},

pages={417--428},

crossref={FOCS26},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS26,

title={26th Annual Symposium on Foundations of Computer Science},

booktitle={26th Annual Symposium on Foundations of Computer

Science},

month={21--23 } # oct,

year=1985,

address={Portland, Oregon},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Article{Vazirani87a,

  author =       {Umesh V. Vazirani},

  title =        {Strong communication complexity or generating quasirandom

sequences from two communicating semirandom sources},

  journal =      {Combinatorica},

  year =         {1987},

  OPTkey =       {},

  volume =       {7},

  number =       {4},

  pages =        {375--392},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Article{ChorGo88,

title={Unbiased Bits from Sources of Weak Randomness and Probabilistic

Communication Complexity},

author={Benny Chor and Oded Goldreich},

pages={230--261},

journal=sicomp,

year=1988,

month=apr,

volume=17,

number=2,

source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}

}







@Misc{SrinivasanZu98,

  OPTcrossref =  "",

  OPTkey =       "",

  author =       "Aravind Srinivasan and David Zuckerman",

  title =        "Computing with Very Weak Random Sources",

  howpublished = "To appear in {\em SIAM Journal on Computing}",

  year =         "1998",

  OPTmonth =     "",

  note =         "Preliminary version in {\em FOCS `94}",

  OPTannote =    ""

}



@InProceedings{RadhakrishnanTa97,

title={Tight bounds for depth-two superconcentrators},

author={Jaikumar Radhakrishnan and Amnon {Ta-S}hma},

pages={585--594},

crossref={FOCS38},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS38,

title={38th Annual Symposium on Foundations of Computer Science},

booktitle={38th Annual Symposium on Foundations of Computer

Science},

month={20--22 } # oct,

year=1997,

address={Miami Beach, Florida},

organization={IEEE},

crossrefonly=1,

pubinfo={IEEE Computer Society Press Order Number PR08197; IEEE Order

Plan Catalog Number 97CH36130; ISBN 0-8186-8197-7; ISBN 0-8186-8198-5

(case); ISBN 0-8186-8199-3 (microfiche); ISSN 0272-5428},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



string{jacm={Journal of the ACM}}



@Article{SaksSrZh98,

title={Explicit {OR}-Dispersers with Polylogarithmic Degree},

author={Michael Saks and Aravind Srinivasan and Shiyu Zhou},

area={Formal Languages and Complexity Theory},

journal=jacm,

pages={123--154},

month=jan,

year=1998,

volume=45,

number=1,

keywords={Derandomization, expander graphs, explicit constructions,

hashing lemmas, hardness of approximation, imperfect sources of

randomness, measures of information, pseudo-random generators,

randomized computation, time-space tradeoffs},

general-terms={Algorithms, Theory},

cr-categories={F.1.3[relations among randomized complexity classes];

G.2.1[combinatorial algorithms]; G.3[probabilistic algorithms]},

preliminary={stoc::SaksSZ1995},

source={http://theory.lcs.mit.edu/~jacm/jacm.bib}

}



@PhdThesis{Vazirani86,

  author =       {Umesh V. Vazirani},

  title =        {Randomness, Adversaries, and Computation},

  school =       {University of California, Berkeley},

  year =         {1984},

  OPTkey =       {},

  OPTtype =      {},

  OPTaddress =   {},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@InProceedings{ImpagliazzoLeLu89,

title={Pseudo-random Generation from one-way functions (Extended

Abstracts)},

author={Impagliazzo, Russell and Levin, Leonid A. and Luby, Michael},

pages={12--24},

crossref={STOC21},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC21,

title={Proceedings of the Twenty First Annual ACM Symposium on Theory

of Computing},

booktitle={Proceedings of the Twenty First Annual ACM Symposium on

Theory of Computing},

month={15--17 } # may,

year=1989,

address={Seattle, Washington},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{Nisan96,

title={Extracting Randomness: How and Why: A Survey},

author={Noam Nisan},

pages={44--58},

crossref={SCTC96},

source={http://theory.lcs.mit.edu/~dmjones/hbp/sctc/concur.bib}

}



@Proceedings{SCTC96,

title={Proceedings, Eleventh Annual IEEE Conference on Computational

Complexity},

booktitle={Proceedings, Eleventh Annual IEEE Conference on

Computational Complexity},

address={Philadelphia, Pennsylvania},

month={24--27~} # may,

year=1996,

publisher={IEEE Computer Society Press},

crossrefonly=1,

comment={checked},

source={http://theory.lcs.mit.edu/~dmjones/hbp/sctc/concur.bib}

}



@Article{NisanTa99,

  author =       {Noam Nisan and Amnon {Ta-Shma}},

  title =        {Extracting Randomness: A Survey and New Constructions},

  journal =      {Journal of Computer and System Sciences},

  year =         {1999},

  OPTkey =       {},

  volume =       {58},

  number =       {1},

  pages =        {148--173},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@InCollection{AjtaiKoStSz89,

  author =       {Mikl{\'o}s Ajtai and J{\'a}nos Koml{\'o}s and William Steiger and

Endre Szemer{\'e}di},

  title =        {Almost Sorting in One Round},

  booktitle =    {Randomness and Computation},

  OPTcrossref =  {},

  OPTkey =       {},

  pages =        {117--125},

  publisher =    {JAI Press Inc.},

  year =         {1989},

  editor =       {Silvio Micali},

  volume =       {5},

  OPTnumber =    {},

  series =       {Advances in Computing Research},

  OPTtype =      {},

  OPTchapter =   {},

  OPTaddress =   {},

  OPTedition =   {},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Article{Pippenger87,

title={Sorting and Selecting in Rounds},

author={Nicholas Pippenger},

pages={1032--1038},

journal=sicomp,

year=1987,

month=dec,

volume=16,

number=6,

source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}

}



@Book{AlonSpEr92,

  author =       {Noga Alon and Joel H. Spencer and Paul Erd{\H{o}}s},

  ALTeditor =    {},

  title =        {The Probabilistic Method},

  publisher =    {John Wiley and Sons, Inc.},

  year =         {1992},

  OPTkey =       {},

  OPTvolume =    {},

  OPTnumber =    {},

  series =       {Wiley-Interscience Series in Discrete Mathematics and

Optimization},

  OPTaddress =   {},

  OPTedition =   {},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Book{Goldreich95,

  author =       {Oded Goldreich},

  ALTeditor =    {},

  title =        {Foundations of Cryptography (Fragments of a Book)},

  publisher =    {Weizmann Institute of Science},

  year =         {1995},

  OPTkey =       {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  OPTaddress =   {},

  OPTedition =   {},

  OPTmonth =     {},

  note =         {Available, along with revised version 1/98, from

\verb|http://theory.lcs.mit.edu/~oded|},

  OPTannote =    {}

}



@Booklet{Goldreich98,

  title =        {{\em Modern Cryptography, Probabilistic Proofs and

Pseudorandomness}},

  OPTkey =       {},

  author =       {Oded Goldreich},

  OPThowpublished = {},

  OPTaddress =   {},

  month =        {June},

  year =         {1998},

  note =         {To be published by {\em Springer}},

  OPTannote =    {}

}



@Book{MotwaniRa95,

  author =       {Rajeev Motwani and Prabhakar Raghavan},

  ALTeditor =    {},

  title =        {Randomized Algorithms},

  publisher =    {Cambridge University Press},

  year =         {1995},

  OPTkey =       {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  OPTaddress =   {},

  OPTedition =   {},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Book{AssmusKe92,

  author =       "E.F. Assmus and J.D. Key",

  title =        "Designs and their codes",

  publisher =    "Cambridge University Press",

  year =         "1992",

  OPTcrossref =  "",

  OPTkey =       "",

  OPTeditor =    "",

  OPTvolume =    "",

  number =       "103",

  series =       "Cambridge Tracts in Mathematics",

  OPTaddress =   "",

  OPTedition =   "",

  OPTmonth =     "",

  OPTnote =      "",

  OPTannote =    ""

}



@Misc{TaShma98b,

  OPTcrossref =  "",

  OPTkey =       "",

  author =       "Amnon {Ta-S}hma",

  OPTtitle =     "",

  howpublished = "Personal communication",

  year =         "1998",

  month =        "August",

  OPTnote =      "",

  OPTannote =    ""

}



@TechReport{SudanTrVa98,

  author =       {Madhu Sudan and Luca Trevisan and Salil Vadhan},

  title =        {Pseudorandom Generators without the {XOR} Lemma},

  institution =  {Electronic Colloquium on Computational Complexity},

  year =         {1998},

  OPTkey =       {},

  OPTtype =      {},

  number =       {TR98-074},

  OPTaddress =   {},

  month =        {December},

  note =         {Extended abstract in these proceedings.},

  OPTannote =    {}

}



@Book{MacWilliamsSl77,

  author =       {Florence J. MacWilliams and Neil J. A. Sloane},

  title =        {The Theory of Error-Correcting Codes},

  publisher =    {North-Holland},

  year =         {1977},

  OPTkey =       {},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  OPTaddress =   {},

  OPTedition =   {},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}



@Article{BellareGoSu98,

title={Free Bits, {PCPs}, and Nonapproximability---Towards Tight

Results},

author={Mihir Bellare and Oded Goldreich and Madhu Sudan},

pages={804--915},

journal=sicomp,

month=jun,

year=1998,

volume=27,

number=3,

siam-key={30253},

preliminary={focs::BellareGS1995, eccc::BellareGS1995},

source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}

}



@Book{CoverTh91,

  author =       "Thomas M. Cover and Joy A. Thomas",

  title =        "Elements of Information Theory",

  publisher =    "John Wiley \& Sons, Inc.",

  year =         "1991",

  OPTcrossref =  "",

  OPTkey =       "",

  OPTeditor =    "",

  OPTvolume =    "",

  OPTnumber =    "",

  series =       "Wiley Series in Telecommunications",

  OPTaddress =   "",

  edition =      "2nd",

  OPTmonth =     "",

  OPTnote =      "",

  OPTannote =    ""

}



@Unpublished{ImpagliazzoWi96,

  author =       {Russell Impagliazzo and Avi Wigderson},

  title =        {An Information Theoretic Variant of the Inclusion-Exclusion

Bound (Preliminary Version)},

  note =         {Unpublished manuscript},

  OPTkey =       {},

  month =        {September},

  year =         {1996},

  OPTannote =    {}

}



@InProceedings{ImpagliazzoWi97,

title={{$\mathit{P} = \mathit{BPP}$} if {$E$} Requires Exponential

Circuits: Derandomizing the {XOR} Lemma},

author={Russell Impagliazzo and Avi Wigderson},

pages={220--229},

crossref={STOC29},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC29,

title={Proceedings of the Twenty-Ninth Annual ACM Symposium on

Theory of Computing},

booktitle={Proceedings of the Twenty-Ninth Annual ACM Symposium on

Theory of Computing},

month={4--6 } # may,

year=1997,

address={El Paso, Texas},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Misc{RazReVa99b,

  OPTkey =       {},

  author =       {Ran Raz and Omer Reingold and Salil Vadhan},

  title =        {Error Reduction in Extractors},

  OPThowpublished = {},

  OPTmonth =     {},

  year =         {1999},

  note =         {In preparation},

  OPTannote =    {}

}



@InProceedings{FriedmanKS89,

title={On the Second Eigenvalue in Random Regular Graphs},

author={Friedman, Joel and Kahn, Jeff and Szemer{\'e}di, Endre},

pages={587--598},

crossref={STOC21},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC21,

title={Proceedings of the Twenty First Annual ACM Symposium on Theory

of Computing},

booktitle={Proceedings of the Twenty First Annual ACM Symposium on

Theory of Computing},

month={15--17 } # may,

year=1989,

address={Seattle, Washington},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{BroderSha87,

title={On the Second Eigenvalue of Random Regular Graphs (Preliminary

Version)},

author={Broder, Andrei and Shamir, Eli},

pages={286--294},

crossref={FOCS28},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@string{jacm={Journal of the ACM}}



@Article{Kahale95,

title={Eigenvalues and Expansion of Regular Graphs},

author={Nabil Kahale},

pages={1091--1106},

area={Graph Theory and Combinatorial Structures},

journal=jacm,

month=sep,

year=1995,

volume=42,

number=5,

general-terms={Algorithms, Theory},

keywords={Eigenvalues, expander graphs, induced subgraphs, load

balancing, Ramanujan graphs, random walks, selection networks},

cr-categories={F.2.2; G.2.2},

preliminary={FOCS::Kahale1991, FOCS::Kahale1992},

source={http://theory.lcs.mit.edu/~jacm/jacm.bib}

}



@Article{AjtaiKoSz83,

   AUTHOR = {Mikl{\'o}s Ajtai and J{\'a}nos Koml{\'o}s and Endre Szemer{\'e}di},

    TITLE = {Sorting in $c\,{\rm log}\,n$ parallel steps},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

             Mathematical Society},

   VOLUME = {3},

     YEAR = {1983},

   NUMBER = {1},

    PAGES = {1--19},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {68P10},

 MRNUMBER = {85d:68017},

   MRREVR = {Ernst-Erich Doberkat},

}



@article{Urquhart87,

   AUTHOR = {Urquhart, Alasdair},

    TITLE = {Hard examples for resolution},

 JOURNAL = {Journal of the Association for Computing Machinery},

   VOLUME = {34},

     YEAR = {1987},

   NUMBER = {1},

    PAGES = {209--219},

     ISSN = {0004-5411},

    CODEN = {JACOAH},

  MRCLASS = {68Q25 (03B05 03B35 03D15 68R10 68T15)},

 MRNUMBER = {89e:68056},

   MRREVR = {Alexander Leitsch},

}





@InCollection{Valiant77,

  author = 	 {Valiant, Leslie G.},

  title = 	 {Graph-theoretic arguments in low-level complexity},

  booktitle = 	 {Mathematical foundations of computer science (Proc. Sixth

             Sympos., Tatransk{\'a} Lomnica, 1977)},

  OPTcrossref =  {},

  OPTkey = 	 {},

  pages =	 {162--176. Lecture Notes in Comput. Sci., Vol. 53},

  publisher =	 {Springer},

  year =	 {1977},

  OPTeditor = 	 {},

  OPTvolume = 	 {},

  OPTnumber = 	 {},

  OPTseries = 	 {},

  OPTtype = 	 {},

  OPTchapter = 	 {},

  address =	 {Berlin},

  OPTedition = 	 {},

  OPTmonth = 	 {},

  OPTnote = 	 {},

  OPTannote = 	 {}

}



@InProceedings{ImpagliazzoNiWi94,

title={Pseudorandomness for Network Algorithms},

author={Russell Impagliazzo and Noam Nisan and Avi Wigderson},

pages={356--364},

crossref={STOC26},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC26,

title={Proceedings of the Twenty-Sixth Annual ACM Symposium on the

Theory of Computing},

booktitle={Proceedings of the Twenty-Sixth Annual ACM Symposium on

the Theory of Computing},

month={23--25 } # may,

year=1994,

address={Montr{\'e}al, Qu{\'e}bec, Canada},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{GoldreichImLeVeZu90,

title={Security Preserving Amplification of Hardness},

author={Goldreich, Oded and Impagliazzo, Russell and Levin, Leonid and

Venkatesan, Ramarathnam and Zuckerman, David},

pages={318--326},

crossref={FOCS31a},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS31a,

title={31st Annual Symposium on Foundations of Computer Science},

booktitle={31st Annual Symposium on Foundations of Computer

Science},

volume={I},

month={22--24 } # oct,

year=1990,

address={St. Louis, Missouri},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Article{NaorNa93,

title={Small-Bias Probability Spaces: Efficient Constructions and

Applications},

author={Joseph Naor and Moni Naor},

pages={838--856},

journal=sicomp,

year=1993,

month=aug,

volume=22,

number=4,

source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}

}



@article{SipserSp96,

   AUTHOR = {Sipser, Michael and Spielman, Daniel A.},

    TITLE = {Expander codes},

  JOURNAL = {IEEE Transactions

             on Information Theory},

   VOLUME = {42},

     YEAR = {1996},

   NUMBER = {6, part 1},

    PAGES = {1710--1722},

     ISSN = {0018-9448},

    CODEN = {IETTAW},

  MRCLASS = {94B05},

 MRNUMBER = {98d:94031},

}



@InProceedings{KarpPiSi85,

  author =       {Richard Karp and Nicholas Pippenger and Michael Sipser},

  title =        {A time-randomness tradeoff},

  booktitle =    {{AMS} Conference on Probabilistic Computational Complexity},



  OPTcrossref =  {},

  OPTkey =       {},

  OPTpages =     {},

  year =         {1985},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Durham, New Hampshire},

  OPTmonth =     {},

  OPTorganization = {},

  OPTpublisher = {},

  OPTnote =      {},

  OPTannote =    {}

}



@article {Spielman96,

   AUTHOR = {Spielman, Daniel A.},

    TITLE = {Linear-time encodable and decodable error-correcting codes},

  JOURNAL = {IEEE Transactions

             on Information Theory},

   VOLUME = {42},

     YEAR = {1996},

   NUMBER = {6, part 1},

    PAGES = {1723--1731},

     ISSN = {0018-9448},

    CODEN = {IETTAW},

  MRCLASS = {94B05 (68Q25)},

 MRNUMBER = {98g:94034},

}



@InProceedings{Pinsker73,

  author =       {Mark S. Pinsker},

  title =        {On the Complexity of a Concentrator},

  booktitle =    {7th Annual Teletraffic Conference},

  OPTcrossref =  {},

  OPTkey =       {},

  pages =        {318/1--318/4},

  year =         {1973},

  OPTeditor =    {},

  OPTvolume =    {},

  OPTnumber =    {},

  OPTseries =    {},

  address =      {Stockholm},

  OPTmonth =     {},

  OPTorganization = {},

  OPTpublisher = {},

  OPTnote =      {},

  OPTannote =    {}

}



@article {Alon86,

   AUTHOR = {Noga Alon},

    TITLE = {Eigenvalues and expanders},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

             Mathematical Society},

   VOLUME = {6},

     YEAR = {1986},

   NUMBER = {2},

    PAGES = {83--96},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {05C50},

 MRNUMBER = {88e:05077},

   MRREVR = {Claude Benzaken},

}



@article{Margulis73,

   AUTHOR = {Margulis, Gregory A.},

    TITLE = {Explicit constructions of expanders},

  JOURNAL = {Problemy Pereda{\v c}i Informacii},

   VOLUME = {9},

     YEAR = {1973},

   NUMBER = {4},

    PAGES = {71--80},

  MRCLASS = {94A15 (22E45)},

 MRNUMBER = {58 #4643},

   MRREVR = {J. S. Joel},

}



@article {Margulis88,

   AUTHOR = {Margulis, Gregory 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 = {89f:68054},

   MRREVR = {Mirko K{\v{r}}iv{\'a}nek},

}



@Article{GabberGa81,

title={Explicit Constructions of Linear-Sized Superconcentrators},

author={Ofer Gabber and Zvi Galil},

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}

}



@article {AlonGaMi87,

   AUTHOR = {Alon, Noga and Galil, Zvi and Milman, Vitali D.},

    TITLE = {Better expanders and superconcentrators},

 JOURNAL = {Journal of Algorithms},

   VOLUME = {8},

     YEAR = {1987},

   NUMBER = {3},

    PAGES = {337--347},

     ISSN = {0196-6774},

    CODEN = {JOALDV},

  MRCLASS = {68Q20 (05C75 68R10)},

 MRNUMBER = {89f:68023},

}



@InProceedings{AlonMi84,

title={Eigenvalues, Expanders and Superconcentrators (Extended

Abstract)},

author={Alon, Noga and Milman, Vitali D.},

pages={320--322},

crossref={FOCS25},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS25,

title={25th Annual Symposium on Foundations of Computer Science},

booktitle={25th Annual Symposium on Foundations of Computer Science},

month={24--26 } # oct,

year=1984,

address={Singer Island, Florida},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@article {JimboMa87,

   AUTHOR = {Shuji Jimbo and Akira Maruoka},

    TITLE = {Expanders obtained from affine transformations},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

             Mathematical Society},

   VOLUME = {7},

     YEAR = {1987},

   NUMBER = {4},

    PAGES = {343--355},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {68R10 (05C99)},

 MRNUMBER = {89d:68071},

   MRREVR = {Mirko K{\v{r}}iv{\'a}nek},

}



@article {LubotzkyPhSa88,

   AUTHOR = {Lubotzky, Alex and Phillips, Ralph and Sarnak, Peter},

    TITLE = {Ramanujan graphs},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

             Mathematical Society},

   VOLUME = {8},

     YEAR = {1988},

   NUMBER = {3},

    PAGES = {261--277},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {05C75 (05C25 05C50)},

 MRNUMBER = {89m:05099},

   MRREVR = {David Riley Witte},

}



@article {Ajtai94,

   AUTHOR = {Ajtai, Mikl{\'o}s},

    TITLE = {Recursive construction for $3$-regular expanders},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal on Combinatorics and

             the Theory of Computing},

   VOLUME = {14},

     YEAR = {1994},

   NUMBER = {4},

    PAGES = {379--416},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {05C38 (05C85)},

 MRNUMBER = {95m:05141},

   MRREVR = {Marek Kubale},

}



@article {AlonMi85,

   AUTHOR = {Alon, Noga and Milman, Vitali D.},

    TITLE = {$\lambda\sb 1,$ isoperimetric inequalities for graphs, and

             superconcentrators},

 JOURNAL = {Journal of Combinatorial Theory. Series B},

   VOLUME = {38},

     YEAR = {1985},

   NUMBER = {1},

    PAGES = {73--88},

     ISSN = {0095-8956},

    CODEN = {JCBTB8},

  MRCLASS = {05C50},

 MRNUMBER = {87b:05092},

}



@Article{Tanner84,

  author =       {Michael R. Tanner},

  title =        {Explicit Concentrators from Generalized $N$-gons},

  journal =      {SIAM Journal on Algebraic Discrete Methods},

  year =         {1984},

  OPTkey =       {},

  volume =       {5},

  number =       {3},

  pages =        {287--293},

  OPTmonth =     {},

  OPTnote =      {},

  OPTannote =    {}

}





@Proceedings{FOCS28,

title={28th Annual Symposium on Foundations of Computer Science},

booktitle={28th Annual Symposium on Foundations of Computer

Science},

month={12--14 } # oct,

year=1987,

address={Los Angeles, California},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@article {Friedman91,

   AUTHOR = {Friedman, Joel},

    TITLE = {On the second eigenvalue and random walks in random $d$-regular

             graphs},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal on Combinatorics and

             the Theory of Computing},

   VOLUME = {11},

     YEAR = {1991},

   NUMBER = {4},

    PAGES = {331--362},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {05C80 (05C50)},

 MRNUMBER = {93i:05115},

   MRREVR = {Lane Clark},

}



@article {Nilli91,

   AUTHOR = {Nilli, A.},

    TITLE = {On the second eigenvalue of a graph},

 JOURNAL = {Discrete Mathematics},

   VOLUME = {91},

     YEAR = {1991},

   NUMBER = {2},

    PAGES = {207--210},

     ISSN = {0012-365X},

    CODEN = {DSMHA4},

  MRCLASS = {05C50},

 MRNUMBER = {92j:05124},

   MRREVR = {Wan Di Wei},

}



@string{jcomp = {Journal of Complexity}}



@Article{ChorGo89,

title={On the Power of Two-Point Based Sampling},

author={Benny Chor and Oded Goldreich},

pages={96--106},

journal=jcomp,

year=1989,

month=mar,

volume=5,

number=1,

source={http://theory.lcs.mit.edu/~dmjones/hbp/jcomp/jcomp.bib}

}

@InProceedings{CohenWi89,

title={Dispersers, Deterministic Amplification, and Weak Random

Sources (Extended Abstract)},

author={Cohen, Aviad and Wigderson, Avi},

pages={14--19},

crossref={FOCS30},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@InProceedings{ImpagliazzoZu89,

title={How to Recycle Random Bits},

author={Impagliazzo, Russell and Zuckerman, David},

pages={248--253},

crossref={FOCS30},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS30,

title={30th Annual Symposium on Foundations of Computer Science},

booktitle={30th Annual Symposium on Foundations of Computer Science},

month={30 } # oct # {--1 } # nov,

year=1989,

address={Research Triangle Park, North Carolina},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@article {Blum86,

   AUTHOR = {Blum, M.},

    TITLE = {Independent unbiased coin flips from a correlated biased

             source---a finite state {M}arkov chain},

     NOTE = {Theory of computing (Singer Island, Fla., 1984)},

  JOURNAL = {Combinatorica},

 FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

             Mathematical Society},

   VOLUME = {6},

     YEAR = {1986},

   NUMBER = {2},

    PAGES = {97--108},

     ISSN = {0209-9683},

    CODEN = {COMBDI},

  MRCLASS = {60J10 (68Q20 90D99)},

 MRNUMBER = {88e:60079},

   MRREVR = {Luc P. Devroye},

}

@InProceedings{AjtaiKoSz87,

title={Deterministic Simulation in {LOGSPACE}},

author={Ajtai, Mikl{\'o}s and Koml{\'o}s, J{\'a}nos and

Szemer{\'e}di, E.},

pages={132--140},

crossref={STOC19},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC19,

title={Proceedings of the Nineteenth Annual ACM Symposium on Theory of

Computing},

booktitle={Proceedings of the Nineteenth Annual ACM Symposium on

Theory of Computing},

month={25--27 } # may,

year=1987,

address={New York City},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@InProceedings{BellareRo94,

title={Randomness-Efficient Oblivious Sampling},

author={Mihir Bellare and John Rompel},

pages={276--287},

crossref={FOCS35},

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@Proceedings{FOCS35,

title={35th Annual Symposium on Foundations of Computer Science},

booktitle={35th Annual Symposium on Foundations of Computer

Science},

month={20--22 } # nov,

year=1994,

address={Santa Fe, New Mexico},

organization={IEEE},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}

}



@article {HastadImLeLu99,

   AUTHOR = {H{\aa}stad, Johan and Impagliazzo, Russell and Levin, Leonid A.

             and Luby, Michael},

    TITLE = {A pseudorandom generator from any one-way function},

  JOURNAL = {SIAM J. Comput.},

 FJOURNAL = {SIAM Journal on Computing},

   VOLUME = {28},

     YEAR = {1999},

   NUMBER = {4},

    PAGES = {1364--1396 (electronic)},

     ISSN = {1095-7111},

  MRCLASS = {65C10 (68P25 68Q25 94A60)},

 MRNUMBER = {2000b:65010},

   MRREVR = {Francesco Fabris},

}



@TechReport{Goldreich97,

  author = 	 {Oded Goldreich},

  title = 	 {A Sample of Samplers: A Computational Perspective on Sampling},

  institution =  {Electronic Colloquium on Computational Complexity},

  year = 	 {1997},

  OPTkey = 	 {},

  OPTtype = 	 {},

  number =	 {TR97-020},

  OPTaddress = 	 {},

  month =	 {May},

  OPTnote = 	 {},

  OPTannote = 	 {}

}



@Article{CanettiEvGo95,

title={Lower bounds for sampling algorithms for estimating the

average},

author={Ran Canetti and Guy Even and Oded Goldreich},

pages={17--25},

journal=ipl,

month={13~} # jan,

year=1995,

volume=53,

number=1,

source={http://theory.lcs.mit.edu/~dmjones/hbp/ipl/ipl.bib}

}







@article {Morgenstern94,

   AUTHOR = {Morgenstern, Moshe},

    TITLE = {Existence and explicit constructions of $q+1$ regular

             {R}amanujan graphs for every prime power $q$},

  JOURNAL = {Journal of Combinatorial Theory. Series B},

   VOLUME = {62},

     YEAR = {1994},

   NUMBER = {1},

    PAGES = {44--62},

     ISSN = {0095-8956},

    CODEN = {JCBTB8},

  MRCLASS = {05C35 (05C25)},

 MRNUMBER = {95h:05089},

   MRREVR = {Marcus du Sautoy},

}









@article {Ustimenko97,

   AUTHOR = {Ustimenko, V. A.},

    TITLE = {Ramanujan graphs of a given degree},

  JOURNAL = {Dopov. Nats. Akad. Nauk Ukr. Mat. Prirodozn. Tekh. Nauki},

 FJOURNAL = {Dopov\={\i} d\={\i}\ Nats\={\i} onal\cprime no{\"\i}\ Akadem\={\i} {\"\i}\

             Nauk Ukra{\"\i} ni. Matematika. Prirodoznavstvo. Tekhn\={\i}

             chn\={\i}\ Nauki},

   VOLUME = {1997},

   NUMBER = {6},

    PAGES = {37--41},

     ISSN = {1025-6415},

  MRCLASS = {05C75},

 MRNUMBER = {98k:05123},

   MRREVR = {Perla L. Myers},

   YEAR = {1997}

}





@Article{PippengerYa82,

  author = 	 {Nicholas Pippenger and Andrew C. Yao},

  title = 	 {Rearrangeable Networks with Limited Depth},

  journal = 	 {{SIAM} Journal on Algebraic and Discrete Methods},

  year = 	 {1982},

  OPTkey = 	 {},

  volume =	 {3},

  OPTnumber = 	 {},

  pages =	 {411--417},

  OPTmonth = 	 {},

  OPTnote = 	 {},

  OPTannote = 	 {}

}



@InProceedings{RazReingoldVa99b,

  author = 	 {Ran Raz and Omer Reingold and Salil Vadhan},

  title = 	 {Error Reduction for Extractors},

  booktitle = 	 {Proceedings of the 40th Annual Symposium on the Foundations of Computer Science},

  year =	 {1999},

  organization = {IEEE},

  month =	 {October},

  OPTpages =	 {},

  address =    {New York, NY},

  OPTnote = {}

}



@InProceedings{FriedmanKaSz89,

title={On the Second Eigenvalue in Random Regular Graphs},

author={Friedman, Joel and Kahn, Jeff and Szemer{\'e}di, Endre},

pages={587--598},

crossref={STOC21},

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}



@Proceedings{STOC21,

title={Proceedings of the Twenty First Annual ACM Symposium on Theory

of Computing},

booktitle={Proceedings of the Twenty First Annual ACM Symposium on

Theory of Computing},

month={15--17 } # may,

year=1989,

address={Seattle, Washington},

c-organization={ACM},

key={ACM},

crossrefonly=1,

source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}

}





@InProceedings{ReingoldShWi00,

  author = 	 {Omer Reingold and Ronen Shaltiel and Avi Wigderson},

  title = 	 {Extracting Randomness via Repeated Condensing},

  OPTbooktitle = 	 {},

  crossref =	 {FOCS41},

  OPTkey = 	 {},

  OPTpages = 	 {},

  OPTyear = 	 {},

  OPTeditor = 	 {},

  OPTvolume = 	 {},

  OPTnumber = 	 {},

  OPTseries = 	 {},

  OPTaddress = 	 {},

  OPTmonth = 	 {},

  OPTorganization = {},

  OPTpublisher = {},

  OPTnote =	 {},

  OPTannote = 	 {}

}

		  

		  



@InProceedings{ReingoldVaWi00,

  author = 	 {Omer Reingold and Salil Vadhan and Avi Wigderson},

  title = 	 "Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree

  Expanders and Extractors (Extended Abstract)",

  crossref =	 {FOCS41},

  OPTkey = 	 "",

  OPTeditor = 	 "",

  OPTvolume = 	 "",

  OPTnumber = 	 "",

  OPTseries = 	 "",

  OPTpages =	 "",

  OPTbooktitle = "",

  OPTyear = 	 "",

  OPTorganization = "",

  OPTpublisher = "",

  OPTaddress = 	 "",

  OPTmonth = 	 "",

  note =	 {See a more complete version in ECCC TR01-018,

\verb|http://www.eccc.uni-trier.de/eccc|},

},

  OPTannote = 	 ""

}



@Proceedings{FOCS41,

title={41st Annual Symposium on Foundations of Computer Science},

booktitle={41st Annual Symposium on Foundations of Computer

Science},

month={12--14 } # nov,

year=2000,

address={Redondo Beach, California},

organization={IEEE},

crossrefonly=1

}



@article {Alon86b,

    AUTHOR = {Alon, Noga},

     TITLE = {Eigenvalues, geometric expanders, sorting in rounds, and

              {R}amsey theory},

   JOURNAL = {Combinatorica},

  FJOURNAL = {Combinatorica. An International Journal of the J{\'a}nos Bolyai

              Mathematical Society},

    VOLUME = {6},

      YEAR = {1986},

    NUMBER = {3},

     PAGES = {207--219},

      ISSN = {0209-9683},

     CODEN = {COMBDI},

   MRCLASS = {05C55 (05B05 68R10)},

  MRNUMBER = {88g:05090},

MRREVIEWER = {Pavol Hell},

}





@article {Shoup90,

   AUTHOR = {Shoup, Victor},

    TITLE = {New algorithms for finding irreducible polynomials over finite

             fields},

 JOURNAL = {Mathematics of Computation},

   VOLUME = {54},

     YEAR = {1990},

   NUMBER = {189},

    PAGES = {435--447},

     ISSN = {0025-5718},

    CODEN = {MCMPAF},

  MRCLASS = {11T06 (11Y16)},

 MRNUMBER = {90j:11135},

   MRREVR = {Melvin M. Sweet},

}





@article {AlonGoHaPe92,

    AUTHOR = {Alon, Noga and Goldreich, Oded and H{\aa}stad, Johan and

              Peralta, Ren{\'e}},

     TITLE = {Simple constructions of almost $k$-wise independent random

              variables},

   JOURNAL = {Random Structures \& Algorithms},

    VOLUME = {3},

      YEAR = {1992},

    NUMBER = {3},

     PAGES = {289--304},

      ISSN = {1042-9832},

   MRCLASS = {94A55 (65C10 68Q30)},

  MRNUMBER = {93k:94006a},

}



@article {ReingoldVaWi02,

    AUTHOR = {Reingold, Omer and Vadhan, Salil and Wigderson, Avi},

     TITLE = {Entropy waves, the zig-zag graph product, and new

              constant-degree expanders},

   JOURNAL = {Ann. of Math. (2)},

  FJOURNAL = {Annals of Mathematics. Second Series},

    VOLUME = {155},

      YEAR = {2002},

    NUMBER = {1},

     PAGES = {157--187},

      ISSN = {0003-486X},

     CODEN = {ANMAAH},

   MRCLASS = {05C50 (60C05)},

  MRNUMBER = {2003c:05145},

MRREVIEWER = {Sandi Klav{\v{z}}ar},

}


@article {Nikolov03,
    AUTHOR = {Nikolov, Nikolay},
     TITLE = {On the commutator width of perfect groups},
   JOURNAL = {Bull. London Math. Soc.},
  FJOURNAL = {The Bulletin of the London Mathematical Society},
    VOLUME = {36},
      YEAR = {2004},
    NUMBER = {1},
     PAGES = {30--36},
      ISSN = {0024-6093},
     CODEN = {LMSBBT},
   MRCLASS = {20E22 (20F12)},
  MRNUMBER = {MR2011975 (2004m:20055)},
MRREVIEWER = {Carlo M. Scoppola},
}




@inproceedings{Ben-SassonSuVaWi03,

 author = {Eli Ben-Sasson and Madhu Sudan and Salil Vadhan and Avi Wigderson},

 title = {Randomness-efficient low degree tests and short PCPs via 

          epsilon-biased sets},

 booktitle = {Proceedings of the thirty-fifth ACM 

              symposium on Theory of computing},

 year = {2003},

 isbn = {1-58113-674-9},

 pages = {612--621},

 location = {San Diego, CA, USA},

 doi = {http://doi.acm.org/10.1145/780542.780631},

 publisher = {ACM Press},

 }





@inproceedings{CapalboReVaWi02,

 author = {Michael Capalbo and Omer Reingold and Salil Vadhan 

           and Avi Wigderson},

 title = {Randomness conductors and constant-degree lossless expanders},

 booktitle = {Proceedings of the thiry-fourth annual ACM symposium on 

              Theory of computing},

 year = {2002},

 isbn = {1-58113-495-9},

 pages = {659--668},

 location = {Montreal, Quebec, Canada},

 doi = {http://doi.acm.org/10.1145/509907.510003},

 publisher = {ACM Press},

 }

@article {Eichler54,

    AUTHOR = {Eichler, Martin},

     TITLE = {Quatern\"are quadratische {F}ormen und die {R}iemannsche

              {V}ermutung f\"ur die {K}ongruenzzetafunktion},

   JOURNAL = {Arch. Math.},

    VOLUME = {5},

      YEAR = {1954},

     PAGES = {355--366},

   MRCLASS = {10.0X},

  MRNUMBER = {16,116d},

MRREVIEWER = {L. Carlitz},

}

@article {Kazhdan67,

    AUTHOR = {Kazhdan, David},

     TITLE = {On the connection of the dual space of a group 

with the structure of its closed subgroups ({R}ussian)},

   JOURNAL = {Funkcional. Anal. i Prilozh.},

    VOLUME = {1},

      YEAR = {1967},

     PAGES = {71--74},

   MRCLASS = {},

  MRNUMBER = {},

MRREVIEWER = {},

}



@incollection {Selberg65,

    AUTHOR = {Selberg, Atle},

     TITLE = {On the estimation of {F}ourier coefficients of modular forms},

 BOOKTITLE = {Proc. Sympos. Pure Math., Vol. VIII},

     PAGES = {1--15},

 PUBLISHER = {Amer. Math. Soc.},

   ADDRESS = {Providence, R.I.},

      YEAR = {1965},

   MRCLASS = {10.20},

  MRNUMBER = {32 \#93},

MRREVIEWER = {J. R. Smart},

}



@article {DiaconisSh94,

    AUTHOR = {Diaconis, Persi and Shahshahani, Mehrdad},

     TITLE = {On the eigenvalues of random matrices},

      NOTE = {Studies in applied probability},

   JOURNAL = {J. Appl. Probab.},

  FJOURNAL = {Journal of Applied Probability},

    VOLUME = {31A},

      YEAR = {1994},

     PAGES = {49--62},

      ISSN = {0021-9002},

     CODEN = {JPRBAM},

   MRCLASS = {60B15 (15A18 15A52 60F05)},

  MRNUMBER = {95m:60011},

MRREVIEWER = {Daniel Rockmore},

}



@incollection {LubotzkyWe93,

    AUTHOR = {Lubotzky, A. and Weiss, B.},

     TITLE = {Groups and expanders},

 BOOKTITLE = {Expanding graphs (Princeton, NJ, 1992)},

    SERIES = {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.},

    VOLUME = {10},

     PAGES = {95--109},

 PUBLISHER = {Amer. Math. Soc.},

   ADDRESS = {Providence, RI},

      YEAR = {1993},

   MRCLASS = {05C25 (20F99 22E40)},

  MRNUMBER = {95b:05097},

}



@article {AlonRo94,

    AUTHOR = {Alon, Noga and Roichman, Yuval},

     TITLE = {Random {C}ayley graphs and expanders},

   JOURNAL = {Random Structures Algorithms},

  FJOURNAL = {Random Structures \& Algorithms},

    VOLUME = {5},

      YEAR = {1994},

    NUMBER = {2},

     PAGES = {271--284},

      ISSN = {1042-9832},

   MRCLASS = {05C50 (05C25 05C80)},

  MRNUMBER = {94k:05132},

MRREVIEWER = {Joseph B. Klerlein},

}



@article {Dixon69,

    AUTHOR = {Dixon, John D.},

     TITLE = {The probability of generating the symmetric group},

   JOURNAL = {Math. Z.},

    VOLUME = {110},

      YEAR = {1969},

     PAGES = {199--205},

   MRCLASS = {60.10 (20.00)},

  MRNUMBER = {40 \#4985},

MRREVIEWER = {R. A. Gangolli},

}



@incollection {BabaiHatyeiKaLuSe90,

    AUTHOR = {Babai, L. and Hetyei, G. and Kantor, W. M. and Lubotzky, A.

              and Seress, {\'A}.},

     TITLE = {On the diameter of finite groups},

 BOOKTITLE = {31st Annual Symposium on Foundations of Computer Science,

              Vol.\ I, II (St.\ Louis, MO, 1990)},

     PAGES = {857--865},

 PUBLISHER = {IEEE Comput. Soc. Press},

   ADDRESS = {Los Alamitos, CA},

      YEAR = {1990},

   MRCLASS = {20D60 (68Q10)},

  MRNUMBER = {1 150 735},

}



@inproceedings{MeshulamWi02,

 author = {Roy Meshulam and Avi Wigderson},

 title = {Expanders from symmetric codes},

 booktitle = {Proceedings of the thiry-fourth annual ACM 

              symposium on Theory of computing},

 year = {2002},

 isbn = {1-58113-495-9},

 pages = {669--677},

 location = {Montreal, Quebec, Canada},

 doi = {http://doi.acm.org/10.1145/509907.510004},

 publisher = {ACM Press},

 }





@article {Klawe84,

    AUTHOR = {Klawe, Maria},

     TITLE = {Limitations on explicit constructions of expanding graphs},

   JOURNAL = {SIAM J. Comput.},

  FJOURNAL = {SIAM Journal on Computing},

    VOLUME = {13},

      YEAR = {1984},

    NUMBER = {1},

     PAGES = {156--166},

      ISSN = {0097-5397},

     CODEN = {SMJCAT},

   MRCLASS = {68R10 (05C99)},

  MRNUMBER = {85k:68077},

}



@article {Ore51,

    AUTHOR = {Ore, Oystein},

     TITLE = {Some remarks on commutators},

   JOURNAL = {Proc. Amer. Math. Soc.},

    VOLUME = {2},

      YEAR = {1951},

     PAGES = {307--314},

   MRCLASS = {20.0X},

  MRNUMBER = {12,671e},

MRREVIEWER = {G. Higman},

}





@incollection {LovaszWi98,

    AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o} and Winkler, Peter},

     TITLE = {Mixing times},

 BOOKTITLE = {Microsurveys in discrete probability (Princeton, NJ, 1997)},

    SERIES = {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.},

    VOLUME = {41},

     PAGES = {85--133},

 PUBLISHER = {Amer. Math. Soc.},

   ADDRESS = {Providence, RI},

      YEAR = {1998},

   MRCLASS = {60J10 (60G40 62L15)},

  MRNUMBER = {99h:60138},

MRREVIEWER = {Mark R. Jerrum},

}



@incollection {LovaszWi95,

    AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o} and Winkler, Peter},

     TITLE = {Mixing of random walks and other diffusions on a graph},

 BOOKTITLE = {Surveys in combinatorics, 1995 (Stirling)},

    SERIES = {London Math. Soc. Lecture Note Ser.},

    VOLUME = {218},

     PAGES = {119--154},

 PUBLISHER = {Cambridge Univ. Press},

   ADDRESS = {Cambridge},

      YEAR = {1995},

   MRCLASS = {05C99 (60J15)},

  MRNUMBER = {96g:05138},

}





@article {LiebeckSha95,

    AUTHOR = {Liebeck, Martin W. and Shalev, Aner},

     TITLE = {The probability of generating a finite simple group},

   JOURNAL = {Geom. Dedicata},

  FJOURNAL = {Geometriae Dedicata},

    VOLUME = {56},

      YEAR = {1995},

    NUMBER = {1},

     PAGES = {103--113},

      ISSN = {0046-5755},

     CODEN = {GEMDAT},

   MRCLASS = {20P05 (20D06 20E18 20G40)},

  MRNUMBER = {96h:20116},

MRREVIEWER = {Michael Szalay},

}



@article {Friedman04,

    AUTHOR = {Friedman, Joel},

     TITLE = {A proof of {A}lon's second eigenvalue conjecture. },

   JOURNAL = {To appear, Memoirs of the AMS},

  FJOURNAL = {},

    VOLUME = {},

      YEAR = {},

    NUMBER = {},

     PAGES = {},

      ISSN = {},

   MRCLASS = {},

  MRNUMBER = {},

MRREVIEWER = {},

}





% lifts



@article{FLP,

 author = {Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson},

 title = {Impossibility of distributed consensus with one faulty process},

 journal = {J. ACM},

 volume = {32},

 number = {2},

 year = {1985},

 issn = {0004-5411},

 pages = {374--382},

 doi = {http://doi.acm.org/10.1145/3149.214121},

 publisher = {ACM Press},

 }

@inproceedings{FLM,

 author = {Michael J. Fischer and Nancy A. Lynch and Michael Merritt},

 title = {Easy impossibility proofs for distributed consensus problems},

 booktitle = {Proceedings of the fourth annual ACM symposium on Principles of distributed computing},

 year = {1985},

 isbn = {0-89791-168-7},

 pages = {59--70},

 location = {Minaki, Ontario, Canada},

 doi = {http://doi.acm.org/10.1145/323596.323602},

 publisher = {ACM Press},

 }

@InProceedings{Angluin,

  author =       "Dana Angluin",

  title =        "Local and global properties in networks of processors

                 (Extended Abstract)",

  crossref =     "STOC12",

  pages =        "82--93",

  year =         "1980",

  bibdate =      "Wed Feb 20 18:33:44 MST 2002",

  bibsource =    "http://portal.acm.org/",

  acknowledgement = ack-nhfb,

}



@Proceedings{STOC12,

  editor =       "ACM",

  booktitle =    "Conference proceedings of the twelfth annual {ACM}

                 Symposium on Theory of Computing: papers presented at

                 the symposium, Los Angeles, California, April 28--30,

                 1980",

  title =        "Conference proceedings of the twelfth annual {ACM}

                 Symposium on Theory of Computing: papers presented at

                 the symposium, Los Angeles, California, April 28--30,

                 1980",

  pages =        "v + 447",

  year =         "1980",

  ISBN =         "0-89791-017-6 (paperback)",

  LCCN =         "QA 76.6 A13 1980",

  bibdate =      "Thu Dec 3 07:11:18 MST 1998",

  note =         "ACM order no. 508800.",

  price =        "US\$17.00 (US\$14.00 to members)",

  acknowledgement = ack-nhfb,

  keywords =     "computational complexity --- congresses; electronic

                 digital computers --- programming --- congresses",

                 crossrefonly=1,

}

@book {Stillwell,

    AUTHOR = {Stillwell, John C.},

     TITLE = {Classical topology and combinatorial group theory},

    SERIES = {Graduate Texts in Mathematics},

    VOLUME = {72},

 PUBLISHER = {Springer-Verlag},

   ADDRESS = {New York},

      YEAR = {1980},

     PAGES = {xii+301},

      ISBN = {0-387-90516-2},

   MRCLASS = {57-01 (20-02 20Fxx 57M99)},

  MRNUMBER = {MR602149 (82h:57001)},

MRREVIEWER = {Jo{\v{z}}e Vrabec},

}



@article {Stallings,

    AUTHOR = {Stallings, John R.},

     TITLE = {Topology of finite graphs},

   JOURNAL = {Invent. Math.},

  FJOURNAL = {Inventiones Mathematicae},

    VOLUME = {71},

      YEAR = {1983},

    NUMBER = {3},

     PAGES = {551--565},

      ISSN = {0020-9910},

     CODEN = {INVMBH},

   MRCLASS = {05C10 (20E05 20E07 57M05)},

  MRNUMBER = {MR695906 (85m:05037a)},

MRREVIEWER = {R. C. Lyndon},

}

@article {Negami,

    AUTHOR = {Negami, Seiya},

     TITLE = {The spherical genus and virtually planar graphs},

   JOURNAL = {Discrete Math.},

  FJOURNAL = {Discrete Mathematics},

    VOLUME = {70},

      YEAR = {1988},

    NUMBER = {2},

     PAGES = {159--168},

      ISSN = {0012-365X},

     CODEN = {DSMHA4},

   MRCLASS = {05C10},

  MRNUMBER = {MR949775 (89d:05066)},

MRREVIEWER = {Joan Hutchinson},

}



@inproceedings{BiluLin04,

 author = {Yonatan Bilu and Nati Linial},

 title = {Constructing Expander Graphs by 2-lifts and 

          Discrepancy vs. Spectral Gap},

 isbn = {},

 pages = {},

 location = {},

 doi = {},

 publisher = {},

 crossref={FOCS45},

 }



@Proceedings{FOCS45,

title={45th Annual Symposium on Foundations of Computer Science},

booktitle={45th Annual Symposium on Foundations of Computer

Science},

month={17-19 } # oct,

year=2004,

address={Rome, Italy},

organization={IEEE},

crossrefonly=1,

}



@article {AmitLin02,

    AUTHOR = {Amit, Alon and Linial, Nathan},

     TITLE = {Random graph coverings. {I}. {G}eneral theory and graph

              connectivity},

   JOURNAL = {Combinatorica},

  FJOURNAL = {Combinatorica. An International Journal on Combinatorics and

              the Theory of Computing},

    VOLUME = {22},

      YEAR = {2002},

    NUMBER = {1},

     PAGES = {1--18},

      ISSN = {0209-9683},

   MRCLASS = {05C80 (05C10 05C40)},

  MRNUMBER = {MR1883559 (2003a:05131)},

MRREVIEWER = {Lauren{\c{t}}iu Modan},

}

@article {AmitLinxx,

    AUTHOR = {Amit, Alon and Linial, Nathan},

     TITLE = {Random graph coverings. {II}. {E}dge expansion},

   JOURNAL = {Combinatorics Probability and Computing, to appear},

  FJOURNAL = {},

    VOLUME = {},

      YEAR = {},

    NUMBER = {},

     PAGES = {},

      ISSN = {},

   MRCLASS = {},

  MRNUMBER = {},

MRREVIEWER = {},

}



@article {AlonLinMat02,

    AUTHOR = {Amit, Alon and Linial, Nathan and Matou{\v{s}}ek,

              Ji{\v{r}}\'\i},

     TITLE = {Random lifts of graphs: independence and chromatic number},

   JOURNAL = {Random Structures Algorithms},

  FJOURNAL = {Random Structures \& Algorithms},

    VOLUME = {20},

      YEAR = {2002},

    NUMBER = {1},

     PAGES = {1--22},

      ISSN = {1042-9832},

   MRCLASS = {05C80 (05C15)},

  MRNUMBER = {MR1871947 (2003a:05132)},

MRREVIEWER = {Zbigniew Palka},

}



@article {BassKulkarni,

    AUTHOR = {Bass, Hyman and Kulkarni, Ravi},

     TITLE = {Uniform tree lattices},

   JOURNAL = {J. Amer. Math. Soc.},

  FJOURNAL = {Journal of the American Mathematical Society},

    VOLUME = {3},

      YEAR = {1990},

    NUMBER = {4},

     PAGES = {843--902},

      ISSN = {0894-0347},

   MRCLASS = {20E08 (05C25 20F32 22E40)},

  MRNUMBER = {MR1065928 (91k:20034)},

MRREVIEWER = {Fr{\'e}d{\'e}ric Paulin},

}



@article {Bol:Iso,

    AUTHOR = {Bollob{\'a}s, B{\'e}la},

     TITLE = {The isoperimetric number of random regular graphs},

   JOURNAL = {European J. Combin.},

  FJOURNAL = {European Journal of Combinatorics},

    VOLUME = {9},

      YEAR = {1988},

    NUMBER = {3},

     PAGES = {241--244},

      ISSN = {0195-6698},

   MRCLASS = {05C80 (05C35)},

  MRNUMBER = {MR947025 (89e:05180)},

MRREVIEWER = {Andrzej Ruci{\'n}ski},

}



@article {ArchRicht,

    AUTHOR = {Archdeacon, Dan and Richter, R. Bruce},

     TITLE = {On the parity of planar covers},

   JOURNAL = {J. Graph Theory},

  FJOURNAL = {Journal of Graph Theory},

    VOLUME = {14},

      YEAR = {1990},

    NUMBER = {2},

     PAGES = {199--204},

      ISSN = {0364-9024},

     CODEN = {JGTHDO},

   MRCLASS = {05C10},

  MRNUMBER = {MR1053603 (91c:05066)},

MRREVIEWER = {Bojan Mohar},

}



@article {GroTuck,

    AUTHOR = {Gross, Jonathan L. and Tucker, Thomas W.},

     TITLE = {Generating all graph coverings by permutation voltage

              assignments},

   JOURNAL = {Discrete Math.},

    VOLUME = {18},

      YEAR = {1977},

    NUMBER = {3},

     PAGES = {273--283},

   MRCLASS = {05C10},

  MRNUMBER = {MR0465917 (57 \#5803)},

MRREVIEWER = {Seth R. Alpert},

}



@book {GroTuck:TGT,

    AUTHOR = {Gross, Jonathan L. and Tucker, Thomas W.},

     TITLE = {Topological graph theory},

 PUBLISHER = {Dover Publications Inc.},

   ADDRESS = {Mineola, NY},

      YEAR = {2001},

     PAGES = {xvi+361},

      ISBN = {0-486-41741-7},

   MRCLASS = {05C10 (20F65 57M15)},

  MRNUMBER = {MR1855951},

}



@article {Kim,

    AUTHOR = {Kim, Jeong Han},

     TITLE = {On {B}rooks' theorem for sparse graphs},

   JOURNAL = {Combin. Probab. Comput.},

  FJOURNAL = {Combinatorics, Probability and Computing},

    VOLUME = {4},

      YEAR = {1995},

    NUMBER = {2},

     PAGES = {97--132},

      ISSN = {0963-5483},

   MRCLASS = {05C15 (05C35)},

  MRNUMBER = {MR1342856 (96f:05078)},

MRREVIEWER = {A. G. Thomason},

}



@article {Leighton,

    AUTHOR = {Leighton, Frank Thomson},

     TITLE = {Finite common coverings of graphs},

   JOURNAL = {J. Combin. Theory Ser. B},

  FJOURNAL = {Journal of Combinatorial Theory. Series B},

    VOLUME = {33},

      YEAR = {1982},

    NUMBER = {3},

     PAGES = {231--238},

      ISSN = {0095-8956},

     CODEN = {JCBTB8},

   MRCLASS = {05C70},

  MRNUMBER = {MR693362 (85a:05068)},

MRREVIEWER = {Jonathan L. Gross},

}



@article {AmitLinMat02,

    AUTHOR = {Amit, Alon and Linial, Nathan and Matou{\v{s}}ek,

              Ji{\v{r}}\'\i},

     TITLE = {Random lifts of graphs: independence and chromatic number},

   JOURNAL = {Random Structures Algorithms},

  FJOURNAL = {Random Structures \& Algorithms},

    VOLUME = {20},

      YEAR = {2002},

    NUMBER = {1},

     PAGES = {1--22},

      ISSN = {1042-9832},

   MRCLASS = {05C80 (05C15)},

  MRNUMBER = {MR1871947 (2003a:05132)},

MRREVIEWER = {Zbigniew Palka},

}



@inproceedings {AmitLinMatRoz01,

    AUTHOR = {Amit, Alon and Linial, Nathan and Matou{\v{s}}ek,

              Ji{\v{r}}{\'{\i}} and Rozenman, Eyal},

     TITLE = {Random lifts of graphs},

 BOOKTITLE = {Proceedings of the Twelfth Annual ACM-SIAM Symposium on

              Discrete Algorithms (Washington, DC, 2001)},

     PAGES = {883--894},

 PUBLISHER = {SIAM},

   ADDRESS = {Philadelphia, PA},

      YEAR = {2001},

   MRCLASS = {05C80 (60C05 68R10)},

  MRNUMBER = {MR1958564},

}



% degree sequence



@article {Talagrand93,

    AUTHOR = {Talagrand, M.},

     TITLE = {Isoperimetry, logarithmic {S}obolev inequalities on the

              discrete cube, and {M}argulis' graph connectivity theorem},

   JOURNAL = {Geom. Funct. Anal.},

  FJOURNAL = {Geometric and Functional Analysis},

    VOLUME = {3},

      YEAR = {1993},

    NUMBER = {3},

     PAGES = {295--314},

      ISSN = {1016-443X},

     CODEN = {GFANFB},

   MRCLASS = {26D15 (05C40 46B09 60B11)},

  MRNUMBER = {MR1215783 (94m:26026)},

MRREVIEWER = {Petr Gurka},

}



@article {Margulis74,

    AUTHOR = {Margulis, G. A.},

     TITLE = {Probabilistic characteristics of graphs with large

              connectivity},

   JOURNAL = {Problemy Pereda\v ci Informacii},

    VOLUME = {10},

      YEAR = {1974},

    NUMBER = {2},

     PAGES = {101--108},

   MRCLASS = {05C99},

  MRNUMBER = {MR0472604 (57 \#12300)},

MRREVIEWER = {Andras Frank},

}



@article {LinialRoz02,

    AUTHOR = {Linial, Nathan and Rozenman, Eyal},

     TITLE = {An extremal problem on degree sequences of graphs},

   JOURNAL = {Graphs Combin.},

  FJOURNAL = {Graphs and Combinatorics},

    VOLUME = {18},

      YEAR = {2002},

    NUMBER = {3},

     PAGES = {573--582},

      ISSN = {0911-0119},

     CODEN = {GRCOE5},

   MRCLASS = {05C07 (05C35 90C35)},

  MRNUMBER = {MR1939075 (2003m:05052)},

}



@article {LinialRozxx,

    AUTHOR = {Linial, Nathan and Rozenman, Eyal},

     TITLE = {Random Lifts of graphs 4: Perfect matching},

   JOURNAL = {Combinatorica, to appear},

}



@article {IsmailescuSte02,

    AUTHOR = {Ismailescu, Dan and Stefanica, Dan},

     TITLE = {Minimizer graphs for a class of extremal problems},

   JOURNAL = {J. Graph Theory},

  FJOURNAL = {Journal of Graph Theory},

    VOLUME = {39},

      YEAR = {2002},

    NUMBER = {4},

     PAGES = {230--240},

      ISSN = {0364-9024},

     CODEN = {JGTHDO},

   MRCLASS = {05C35 (05C07 05C75)},

  MRNUMBER = {MR1894468 (2003e:05066)},

MRREVIEWER = {Robert C. Brigham},

}



@inproceedings{RozenmanShaWig04,

 author = {Eyal Rozenman and Aner Shalev and Avi Wigderson},

 title = {A new family of Cayley expanders (?)},

 booktitle = {Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},

 year = {2004},

 isbn = {1-58113-852-0},

 pages = {445--454},

 location = {Chicago, IL, USA},

 doi = {http://doi.acm.org/10.1145/1007352.1007423},

 publisher = {ACM Press},

 }

@proceedings{STOC36,

  editor    = {L{\'a}szl{\'o} Babai},

  title     = {Proceedings of the 36th Annual ACM Symposium on Theory of Computing,

               Chicago, IL, USA, June 13-16, 2004},

  booktitle = {STOC},

  publisher = {ACM},

  year      = {2004},

  isbn      = {1-58113-852-0},

  bibsource = {DBLP, http://dblp.uni-trier.de}

}





@article {Frieze,

    AUTHOR = {Frieze, Alan},

     TITLE = {Hamilton cycles in the union of random permutations},

   JOURNAL = {Random Structures Algorithms},

  FJOURNAL = {Random Structures \& Algorithms},

    VOLUME = {18},

      YEAR = {2001},

    NUMBER = {1},

     PAGES = {83--94},

      ISSN = {1042-9832},

   MRCLASS = {05C45},

  MRNUMBER = {MR1799804 (2002a:05163)},

MRREVIEWER = {E. Rodney Canfield},

}



@book {LovPlum,

    AUTHOR = {Lov{\'a}sz, L. and Plummer, M. D.},

     TITLE = {Matching theory},

    SERIES = {North-Holland Mathematics Studies},

    VOLUME = {121},

      NOTE = {Annals of Discrete Mathematics, 29},

 PUBLISHER = {North-Holland Publishing Co.},

   ADDRESS = {Amsterdam},

      YEAR = {1986},

     PAGES = {xxvii+544},

      ISBN = {0-444-87916-1},

   MRCLASS = {90C10 (05B35 05C70 90C05)},

  MRNUMBER = {MR859549 (88b:90087)},

MRREVIEWER = {Knut Richter},

}

@article {Gross77,
    AUTHOR = {Gross, Jonathan L.},
     TITLE = {Every connected regular graph of even degree is a {S}chreier
              coset graph},
   JOURNAL = {J. Combinatorial Theory Ser. B},
    VOLUME = {22},
      YEAR = {1977},
    NUMBER = {3},
     PAGES = {227--232},
   MRCLASS = {05C25},
  MRNUMBER = {MR0450121 (56 \#8419)},
MRREVIEWER = {A. T. White},
}

@misc{Kassabov05,
     author    = "Martin Kassabov",
     title     = "Symmetric Groups and Expander Graphs",
     HOWPUBLISHED = {Available at http://arxiv.org/abs/math.GR/0505624},
     URL = {http://arxiv.org/abs/math.GR/0505624}  
}
@misc{Kassabov_lattices05,
     author    = "Martin Kassabov",
     title     = "Universal lattices and unbounded rank expanders",
     HOWPUBLISHED = {Available at http://arxiv.org/abs/math.GR/0502237},
     URL = {http://arxiv.org/abs/math.GR/0502237}
}
@misc{NikolovKa05,
     author    = "Martin Kassabov and Nikolay Nikolov",
     title     = "Universal lattices and Property $\tau$",
     HOWPUBLISHED = {Available at http://arxiv.org/abs/math.GR/0502112},
     URL = {http://arxiv.org/abs/math.GR/0502112}
}