@string{focs89="Proc.30th FOCS"}
@string{focs99="Proc. 40th FOCS"}
@string{focs00="Proc. 41st FOCS"}
@string{focs01="Proc. 42nd FOCS"}
@string{focs02="Proc. 43rd FOCS"}
@string{focs04="Proc. 45th FOCS"}
@string{focs05="Proc. 46th FOCS"}

@string{stoc87="Proc. 19th STOC"}
@string{stoc94="Proc. 26th STOC"}
@string{stoc00="Proc. 32nd STOC"}
@string{stoc05="Proc. 37th STOC"}

@string{random06="Proc. 10th Intern. Workshop on Randomization and Computation (RANDOM)"}

@string{crypto02="Proc. 22nd Annual Intern. Cryptology Conf. (CRYPTO)"}
@string{crypto03="Proc. 23rd Annual Intern. Cryptology Conf. (CRYPTO)"}

@string{algor       = "Algorithmica"}
@string{camb        = "Cambridge University Press"}
@string{comb        = "Combinatorica"}
@string{complex     = "Computational Complexity"}
@string{cpc	= "Combinatorics, Probability, and Computing"}
@string{dm      = "Discrete Mathematics"}
@string{ieeeit      = "IEEE Transactions on Information Theory"}
@string{jcss        = "Journal of Computer and System Sciences"}
@string{rsa     = "Random Structures and Algorithms"}

@article{afwz,
    author = "N. Alon and U. Feige and A. Wigderson and D. Zuckerman",
    title = "Derandomized Graph Products",
    journal = complex,
    year = "1995",
    volume = "5",
    pages = "60--75",
    eprint="springer:r591795p150lj86q"}

@inproceedings{aks:space,
    author = "M. Ajtai and J. Koml\'{o}s and E. Szemer\'{e}di",
    title = {Deterministic simulation in {LOGSPACE}},
    booktitle = stoc87,
    year = "1987",
    pages = "132--140",
    eprint="stoc:28395.28410"}

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

@inproceedings{biw,
	author	= "B. Barak and R. Impagliazzo and A. Wigderson",
	title	= "Extracting Randomness Using Few Independent Sources",
	booktitle=focs04,
	year	= "2004",
	pages	= "384--393",
	eprint="focs:10.1109/FOCS.2004.29"}

@inproceedings{bkssw,
	author	= "B. Barak and G. Kindler and R. Shaltiel and B. Sudakov
		and A. Wigderson",
	title	= "Simulating Independence:  New Constructions of
		Condensers, {R}amsey Graphs, Dispersers, and Extractors",
	booktitle=stoc05,
	year	= "2005",
	pages	= "1--10",
	eprint="stoc:1060590.1060592"}

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

@InProceedings{BelS,
	title={Improved Non-Approximability Results},
	author={M. Bellare and M. Sudan},
	pages={184--193},
	booktitle = stoc94,
	year = "1994",
	eprint="stoc:195058.195129"}

@article{BopH,
	author = "R. Boppana and M. Halldorsson",
	title = "Approximating Maximum Independent Sets by Excluding Subgraphs",
	journal = "Bit",
	volume = "32",
	pages = "180--196",
	year = "1992"}

@article{Bou:more,
	author	= "J. Bourgain",
	title	= "More on the Sum-Product Phenomenon in Prime Fields and
			its Applications",
	journal	= "International Journal of Number Theory",
	year	= "2005",
	volume	= "1",
	pages	= "1--32",
	eprint="worldsci:10.1142/S1793042105000108"}

@article{bgk,
	author=	"J.~Bourgain and A.~Glibichuk and S.~Konyagin",
	title=	"Estimates for the number of sums and products and for 
		exponential sums in fields of prime order",
	journal="Journal of the London Mathematical Society",
	volume ="73",  
	pages=	"380--398",
	year=	"2006",
	eprint="cambridge:10.1112/S0024610706022721"}

@article{bkt,
	author	= "J. Bourgain and N. Katz and T. Tao",
	title	= "A Sum-Product Estimate in Finite Fields, and Applications",
	journal = "Geometric and Functional Analysis",
	year	= "2004",
	volume	= "14",
	pages	= "27--57",
	eprint="springer:s00039-004-0451-1"}

@inproceedings{cdhks,
    author = "R. Canetti and Y. Dodis and S. Halevi and E. Kushilevitz and A. Sahai",
    title = "Exposure-Resilient Functions and All-or-Nothing Transforms",
    editor = {Bart Preneel},
    booktitle  = {Proc. Intern. Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT)},
    series = "Lecture Notes in Computer Science",
    volume = "1807",
    pages = "453--469",
    year = "2000",
    month = May,
    publisher  = {Springer-Verlag},
    eprint="springer:mfkb4le6cayk9npb"}

@article{cg:weak,
    author = "B. Chor and O. Goldreich",
    title = "Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity",
    journal = sicomp,
    volume = "17",
    number = "2",
    pages = "230--261",
    year = "1988",
    eprint="sicomp:10.1137/0217015"}

@inproceedings{CohW,
    author = "A. Cohen and A. Wigderson",
    title = "Dispersers, Deterministic Amplification, and Weak Random Sources",
    booktitle = focs89,
    year = "1989",
    pages = "14--19"}

@article{Din,
        author= "I.H. Dinwoodie",
        title=  "A Probability Inequality for the Occupation Measure
                of a Reversible Markov Chain",
        journal="Annals of Applied Probability",
        year=   "1995",
        volume= "5", 
        pages=  "37--43"}       

@inproceedings{DodS,
    author = "Y. Dodis and J. Spencer",
    title = "On the (non)Universality of the One-Time Pad",
    booktitle = focs02,
    year = "2002",
    pages = "376--385",
    eprint="focs:10.1109/SFCS.2002.1181962"}

@techreport{DviR,
    author = "Z. Dvir and R. Raz",
        title = {Analyzing Linear Mergers},
    institution = {Electronic Colloquium on Computational Complexity},
    number = {TR05-025},
    year = "2005",
    eprint="eccc:TR05-025"}

@article{EngH,
	author = "L. Engebretsen and J. Holmerin",
	title = "Towards Optimal Lower Bounds for Clique and Chromatic
			Number",
	journal = tcs,
	volume = "299",
	year = "2003",
	pages = "537--584",
	eprint="tcs:10.1016/S0304-3975(02)00535-2"}

@article{f:theta,
	author	= "U. Feige",
	title	= "Randomized Graph Products, Chromatic Numbers, and the 
		{L}ovasz $\theta$ Function",
	journal	= comb,
	volume	= "17",
	pages	= "79--90", 
	year	= "1997",
	eprint="springer:x785787h43724566"}

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

@article{fk,
	author	="U. Feige and J. Kilian",
	title	="Zero Knowledge and the Chromatic Number",
	journal	=jcss,
	volume	="57",
	year	="1998",
	pages	="187--199",
	eprint="jcss:10.1006/jcss.1998.1587"}

@article{FiaN,
	author =	"A. Fiat and M. Naor",
	title = 	"Implicit {$O(1)$} Probe Search",
	journal	=	sicomp,
	volume = 	"22",
	year = 		"1993",
	pages = 	"1--10",
	eprint="sicomp:10.1137/0222001"}

@article{GabG,
    author = {O. Gabber and Z. Galil},
    title = "Explicit Construction of Linear Sized Superconcentrators",
    journal = jcss,
    volume = "22",
    year = "1981",
    pages = "407-420",
    eprint="jcss:10.1016/0022-0000(81)90040-4"}

@article{Gil,
    author = "D. Gillman",
    title = "A {Chernoff} Bound for Random Walks on Expander Graphs",
    journal = sicomp,
    year = "1998",
    volume = "27",
    pages = "1203--1220",
    eprint="sicomp: 10.1137/S0097539794268765"}

@techreport{Gol:sampler-survey,
    author = "O. Goldreich",
        title = {A Sample of Samplers -- 
	A Computational Perspective on Sampling (survey)},
    institution = {Electronic Colloquium on Computational Complexity},
    number = {TR97-020},
    year = "1997",
    eprint="eccc:TR97-020"}

@techreport{GolZ,
    author = "O. Goldreich and D. Zuckerman",
        title = {Another Proof that {B}{P}{P} $\subseteq$ {P}{H}
        (and more)},
    institution = {Electronic Colloquium on Computational Complexity},
    number = {TR97-045},
    year = "1997",
    eprint="eccc:TR97-045"}

@unpublished{Gre:sumprod,
    author = "B. Green",
    title = {Sum-Product Estimates},
    note = {Unpublished lecture notes.  Available at author's website},
    year = {2005}
    }

@article{Hal,
	author 	= "M. Halldorsson",
	title	= "A Still Better Performance Guarantee for Approximate Graph 
			Coloring",
	journal	= ipl,
	volume	= "45",
	pages	= "19--23",
	year	= "1993",
	eprint="ipl:10.1016/0020-0190(93)90246-6"}

@article{Has:clique,
    author = "J. H{\aa}stad",
    title = "Clique is Hard to Approximate within $n^{1-\epsilon}$",
    journal = "Acta Mathematica",
    volume = "182",
    year = "1999",
    pages = "105--142",
    eprint="springer:m68h3576646ll648"}

@inproceedings{HasK,
	author=	"J. Hastad and S. Khot",
	title=	"Query Efficient {PCP}s with Perfect Completeness",
	booktitle=focs01,
	year=	"2001",
	pages=	"610--619",
	eprint="focs:10.1109/SFCS.2001.959937"}

@inproceedings{Hea,
        author= "A. Healy",
        title=  "Randomness-Efficient Sampling within ${NC}^1$",
        booktitle=random06,
        year=   2006,
	pages="398--409",
	eprint="springer:b773545612310728"}

@article{hlw,
	author=	"S. Hoory and N. Linial and A. Wigderson",
	title=	"Expander Graphs and Their Applications",
	journal="Bulletin of the American Mathematical Society",
	volume=	"43",
	year=	"2006",
	pages=	"439--561",
	url="http://www.ams.org/bull/2006-43-04/S0273-0979-06-01126-8/"}

@inproceedings{iz,
    author = "R. Impagliazzo and D. Zuckerman",
    title = "How to Recycle Random Bits",
    booktitle = focs89,
    year = "1989",
    pages = "248--253"}

@article{Kah,
author = "N. Kahale",
title = "Eigenvalues and Expansion of Regular Graphs",
journal = jacm,
volume = "42",
year = "1995",
pages = "1091--1106",
eprint="jacm:210118.210136"}

@article{Kah:deviation,
author = "N. Kahale",
title	= "Large Deviation Bounds for {M}arkov Chains",
journal	= cpc,
volume	= "6",
year	= "1997",
pages	= "465--474",
eprint="cambridge:10.1017/S0963548397003209"}

@InCollection{Karp:reduce,
  author =       "R. M. Karp",
  title =        "Reducibility Among Combinatorial Problems",
  booktitle =    "Complexity of Computer Computations",
  publisher =    "Plenum Press",
  year =         1972,
  editor =       "R. E. Miller and J. W. Thatcher",
  pages =        "85--103",
  address =      "New York"}

@techreport{KatS,
	author	= "N. Katz and C.-Y. Shen",
	title	= "Garaev's Inequality in Finite Fields Not of
		Prime Order",
	institution="Arxiv",
	year	= "2007",
	eprint="arxiv:math.NT/0703676"}

@inproceedings{Khot:clique,
	author = "S. Khot",
	title = "Improved Inapproximability Results for {MaxClique},
		{Chromatic Number} and {Approximate Graph Coloring}",
	booktitle = focs01,
	year = "2001",
	pages = "600--609",
	eprint="focs:10.1109/SFCS.2001.959936"}

@article{Lov:fractional,
	author	= "L. Lovasz",
	title	= "On the Ratio of the Optimal Integral and Fractional
			Covers",
	journal	= dm,
	volume	= "13",
	year	= "1975",
	pages	= "383--390"}

@article{lps,
    author = "A. Lubotzky and R. Philips and P. Sarnak",
    title = "Ramanujan Graphs",
    journal = comb,
    volume = "8",
    year = "1988",
    pages = "261--277",
    eprint="springer:k285687344657q53"}

@inproceedings{lu:crypto,
    author="C.-J. Lu",
    title = "Hyper-Encryption Against Space-Bounded Adversaries from
        On-Line Strong Extractors",
    booktitle  = crypto02,
    year = "2002",
    pages="257--271",
    eprint="springer:c0hllvfbl0f3fgr5"}

@article{ly,
        author = {C. Lund and M. Yannakakis},
        title = {On the Hardness of Approximating Minimization Problems},
        journal = jacm,
        year = {1994},
	volume = {41},
        pages = {960--981},
	eprint="jacm:185675.306789"}

@article{Mar:Ramanujan,
author = "G.A. Margulis",
title = "Explicit Group Theoretical Constructions of Combinatorial
Schemes and Their Application to the Design of Expanders and
Superconcentrators",
journal = "Problems of Information Transmission",
volume = "24",
pages = "39--46",
year = "1988"}

@article{Mor:Ramanujan,
	author=	"M. Morgenstern",
	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",
	pages=	"44--62",
	eprint="elsevier:10.1006/jctb.1994.1054"}

@article{MosU,
    author = "E. Mossel and C. Umans",
    title = "On the Complexity of Approximating the {VC} Dimension",
    journal = jcss,
    pages = "660--671",
    volume = "65",
    year = "2002",
    eprint="jcss:10.1016/S0022-0000(02)00022-3"}

@Article{nt,
  author =       "N. Nisan and A. {Ta-S}hma",
  title =        "Extracting Randomness: {A} Survey and New Constructions",
  journal =      jcss,
  volume =       "58",
  year =         "1999",
  pages =    "148--173",
  eprint="jcss:10.1006/jcss.1997.1546"}

@article{nz,
    author = "N. Nisan and D. Zuckerman",
        title = "Randomness is Linear in Space",
    journal = jcss,
    volume = "52",
    number = "1",
    year = "1996",
    pages = "43--52",
    eprint="jcss:10.1006/jcss.1996.0004"}

@Article{Pip,
author =       "N. Pippenger",
title =        "Sorting and Selecting in Rounds",
journal =      sicomp,
volume =       "16",
number =       "6",
pages =        "1032--1038",
month =        dec,
year =         "1987",
eprint="sicomp:10.1137/0216066"}

@inproceedings{Raz:extract,
    author = "R. Raz",
    title = {Extractors with Weak Random Seeds},
    booktitle = stoc05,
    year = "2005",
    pages = "11--20",
    eprint="stoc:1060590.1060593"}

@InProceedings{rsw,
  author =   {O. Reingold and R. Shaltiel and A. Wigderson},
  title =    {Extracting Randomness via Repeated Condensing},
  booktitle =    focs00,
  year =         "2000",
  pages =   "22--31",
  eprint="focs:10.1109/SFCS.2000.892008"}

@article{rz,
    author = "A. Russell and D. Zuckerman",
    title = "Perfect-Information Leader Election in $\log^* n + {O}(1)$
            Rounds",
    journal = jcss,
    volume = "63",
    year = "2001",
    pages = "612--626",
    eprint="jcss:10.1006/jcss.2001.1776"}

@inproceedings{SamT,
	author=	"A. Samorodnitsky and L. Trevisan",
	title=	"A {PCP} Characterization of {NP} with Optimal Amortized
			Query Complexity",
	booktitle=stoc00,
	year=	"2000",
	pages=	"191--199",
	eprint="stoc:335305.335329"}

@article{Sha:survey,
	author=	"R. Shaltiel",
	title=	"Recent Developments in Explicit Constructions of Extractors",
	journal="Bulletin of the European Association for Theoretical
			Computer Science",
	volume=	"77",
	year=	"2002",
	month=	"June",
	pages=	"67--95",
	url="www.cs.haifa.ac.il/~ronen/online_papers/survey.ps"}

@article{Sip,
    author = {M. Sipser},
    title =  {Expanders, Randomness, or Time versus Space},
    journal = jcss,
    volume = 36,
    year = {1988},
    pages = "379--383",
    eprint="jcss:10.1016/0022-0000(88)90035-9"}

@book{tv-book,
	author=	"T. Tao and V. Vu",
	title=	"Additive Combinatorics",
	publisher=camb,
	year=	"2006"}

@article{tuz,
    author = "A. {Ta-S}hma and C. Umans and D. Zuckerman",
    title = "Lossless Condensers, Unbalanced Expanders, and Extractors",
    journal = comb,
    volume = "27",
    year = "2007",
    pages = "213--240",
    eprint="springer:y86m43u236782602"}

@article{tz:code,
    author = "A. {Ta-S}hma and D. Zuckerman",
    title = "Extractor Codes",
    journal=ieeeit,
    volume="50",
    year="2004",
    pages="3015--3025",
    eprint="ieee:10.1109/TIT.2004.838377"}

@article{tzs,
    author = "A. {Ta-S}hma and D. Zuckerman and S. Safra",
    title = "Extractors from {R}eed-{M}uller Codes",
    journal = jcss,
    year = "2006",
    volume=72,
    pages = "786--812",
    eprint="jcss:10.1016/j.jcss.2005.05.010"}

@inproceedings{U:unapprox,
author="C. Umans",
title="Hardness of Approximating {$\Sigma_2^p$} Minimization
                  Problems",
booktitle=focs99,
year="1999",
pages = "465--474",
eprint="focs:10.1109/SFFCS.1999.814619"}

@inproceedings{v:local,
    author = {S. Vadhan},
    title = {On Constructing Locally Computable Extractors and Cryptosystems
        in the Bounded Storage Model},
    year = "2003",
    booktitle = crypto03,
    pages="61--77",
    eprint="springer:c169t5w8lmdy6dka"}

@inproceedings{wx,
	author=	"A. Wigderson and D. Xiao",
	title =	"A Randomness-Efficient Sampler for Matrix-Valued Functions
			and Applications",
	booktitle=focs05,
	year  = "2005",
	pages="397--406",
	eprint="focs:10.1109/SFCS.2005.8"}

@article{wz,
    author = "A. Wigderson and D. Zuckerman",
    title  = "Expanders that Beat the Eigenvalue Bound:
            Explicit Construction and Applications",
    journal = comb,
    volume = "19",
    number = "1",
    year = "1999",
    pages = "125--138",
    eprint="springer:wcjlnyjmdxf30b9x"}

@article{Zbpp,
    author = "D. Zuckerman",
    title = "Simulating {BPP} Using a General Weak Random Source",
    journal = algor,
    volume = "16",
    year = "1996",
    pages = "367--391",
    eprint="algorithmica:kx95d4u1jvyxh882"}

@article{Zsamp,
    author = "D. Zuckerman",
    title = "Randomness-Optimal Oblivious Sampling",
    journal = rsa,
    volume = "11",
    pages = "345--367",
    year = "1997",
    eprint="wiley:10.1002/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z"}

@phdthesis{Zthesis,
    Author  = "D. Zuckerman",
    Title   = "Computing Efficiently Using General Weak Random Sources",
    school  = {University of California at Berkeley},
    Year    = "1991"}