% 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}
}