%% revised: LB 2008-05-06, DB 2008-05-12

@string{jacm={J. ACM}}
@string{jcss={J. Computer and System Sciences}}


@article{BeckSpencer, 
  author = "J{\'o}zsef Beck and Joel Spencer",
  title = "Integral Approximation Sequences",
  journal = "Mathematical Programming",
  volume = "30",
  number = "1",
  year = "1984",
  pages = "88--98",
  publisher = "Springer Berlin / Heidelberg",
  eprint="springer:d77488n21q0222p0"}

@InProceedings{Goldreich-Sudan,     
 author =       "Oded Goldreich and Madhu Sudan",
 title =        "Locally testable codes and {PCP}s of almost-linear length",
 booktitle =    "Proc. 43rd FOCS",
 pages =        "13--22",
 year =         "2002",
 publisher =    "IEEE Computer Society Press",
 organization = "IEEE Computer Society",
 address =      "Los Alamitos-Washington-Brussels-Tokyo",
 acknowledgement = "LEABib --- Lehrstuhl f{\"u}r Effiziente Algorithmen
                der Technischen Universit{\"a}t M{\"u}nchen.
                http://wwwmayr.informatik.tu-muenchen.de/leabib",
 cdate =        "1970-01-01",
  mdate =        "1970-01-01",
eprint="focs:10.1109/SFCS.2002.1181878"
}

@article{Shor1,           
  author = "N.Z. Shor",
  title = "Cut-off method with space extension in convex programming problems",
  journal = "Cybernetics and Systems Analysis",
  volume = "13",
  year = "1977",
  pages = "94--96",
eprint="springer:w88055332t2p4215"}

@article{Shor2,
  author = "N.Z. Shor",
  title = "Quadratic optimization problems",
  journal = "Soviet Journal of Circuits and Systems Sciences",
  volume = "25",
  year = "1987",
  pages = "1--11"}

@article{NemYu,            
  author = "D. B. Yudin and A. S. Nemirovski",
  title = "Informational complexity and efficient methos for solving complex extremal problems",
  journal = "Matekon",
  volume = "13",
  year = "1977",
  pages = "25--45"}

@phdthesis{SpielmanThesis,      
  author = "Daniel Spielman",
  title = "Computationally Efficient Error-Correcting Codes and Holographic Proofs",
  year = "1995",
  school = "{M.I.T.}",
  ps="http://cs-www.cs.yale.edu/homes/spielman/PAPERS/thesis.ps",
  pdf="http://cs-www.cs.yale.edu/homes/spielman/PAPERS/thesis.pdf"}

@book{kato,
  author = "T. Kato",
  title = "Perturbation theory for linear operators",
  publisher = "Springer-Verlag",
  year = "1980" }


@article{Golden,          
  author = "S. Golden",
  title = "Lower Bounds for the {H}elmholtz Function",
  journal = "Physical Review",
  volume = "137B",
  number = "4",
  pages = "B1127--1128",
  year = "1965",
  eprint="doi:10.1103/PhysRev.137.B1127"}

@article{Thompson,        
  author = "C. J. Thompson",
  title = "Inequality with Applications in Statistical Mechanics",
  journal = "Journal of Mathematical Physics",
  volume = 6,
  number = 11,
  pages = "1812--1823",
  year = 1965,
  doi = {10.1063/1.1704727},
  url="http://link.aip.org/link/?JMAPAQ/6/1812/1"}

@article{VanBoyd,        
  author = "L. Vandenberghe and S. Boyd",
  title = "Semidefinite Programming",
  journal = "{SIAM} Review",
  volume = "38",
  year = "1996",
  month = "March",
  pages = "49--95",
  eprint="sirev:10.1137/1038003"}

@Article{SchulLoh,      
   author = {Po-Shen Loh and Leonard J. Schulman},
   title = {Improved Expansion of Random {C}ayley Graphs},
   keywords = {expander graphs, Cayley graphs, second eigenvalue, logarithmic generators},
 journal = {Discrete Mathematics and Theoretical Computer Science},
 year = 2004,
 volume = {6},
 number = {2},
 pages = {523-528},
 url = {http://www.dmtcs.org/volumes/abstracts/dm060222.abs.html}
}


@article{ bilu-hypergraph,   
  author = "Yonatan Bilu and Shlomo Hoory",
  title = "On codes from hypergraphs",
  journal = "European Journal of Combinatorics",
  volume = "25",
  number = "3",
  year = "2004",
  pages = "339--354",
  eprint="elsevier:10.1016/j.ejc.2003.10.002"}

@article{RusLan,        
  author = "Zeph Landau and Alexander Russell",
  title = "Random {C}ayley graphs are expanders: a simplified proof of the {A}lon-{R}oichman theorem",
  journal = "The Electronic Journal of Combinatorics",
  volume = "11",
  number = "1",
  year = "2004",
  pdf="http://www.combinatorics.org/Volume_11/PDF/v11i1r62.pdf",
  ps="http://www.combinatorics.org/Volume_11/PostScriptfiles/v11i1r62.ps"}

@article{AW,    
  author = "Rudolf Ahlswede and Andreas Winter",
  title = "Strong Converse for Identification via Quantum Channels",
  journal = "IEEE Transactions on Information Theory",
  volume = "48",
  number = "3",
  year = "2002",
  pages = "569--579",
  eprint="ieee:10.1109/18.985947"}

@article{ goldreich97sample,   
    author = "Oded Goldreich",
    title = "A Sample of Samplers - A Computational Perspective on Sampling (survey)",
    journal = "Electronic Colloquium on Computational Complexity (ECCC)",
    volume = "4",
    number = "020",
    year = "1997",
    url = "citeseer.ist.psu.edu/goldreich97sample.html",
    eprint="eccc:TR97-020"}

@article{ AR,   
    author = "Noga Alon and Yuval Roichman",
    title = "Random {C}ayley Graphs and Expanders",
    journal = "Random Structures \& Algorithms",
    volume = "5",
    year = "1994",
    url = "http://citeseer.ist.psu.edu/alon97random.html" }


@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},
booktitle = {Proc. 31st FOCS},
publisher = {IEEE Computer Society Press},
year = {1990},
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},
eprint="sicomp:10.1137/0222053"
}

@InProceedings{SW,    
 author = "Amir Shpilka and Avi Wigderson",
 title = "Derandomizing homomorphism testing in general groups",
 pages = "427--435",
title = {Proc. 36th STOC},
booktitle = {Proc. 36th STOC},
publisher = {ACM Press},
year = {2004},
 eprint="stoc:10.1145/1007352.1007421"} 

@InProceedings{AroraSa92,
  author =       "Sanjeev Arora and Shmuel Safra",
  title =        "Probabilistic checking of proofs; a new
                 characterization of {NP}",
  pages =        "2--13",
  year =         "1992",
booktitle = {Proc. 33rd FOCS},
publisher = {IEEE Computer Society Press},
year = {1992},
}

@Article{AroraLuMoSuSz98,   
  title =        "Proof Verification and the Hardness of Approximation
                 Problems",
  author =       "Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu Sudan and Mario Szegedy",
  area =         "Formal Languages and Complexity Theory",
  journal =      jacm,
  pages =        "501--555",
  month =        may,
  year =         "1998",
  volume =       "45",
  number =       "3",
  keywords =     "NP-completeness, optimization, proof verification,
                 randomness",
  general-terms = "Algorithms, Theory",
  cr-categories = "F.1.2; F.1.3; F.2.1; F.2.2; F.4.1",
}

@article{ AFWZ,   
    author = "Noga Alon and Uriel Feige and Avi Wigderson and David Zuckerman",
    title = "Derandomized Graph Products",
    journal = "Computational Complexity",
    volume = "5",
    number = "1",
    pages = "60--75",
    year = "1995",
    url = "citeseer.ist.psu.edu/alon96derandomized.html",
    eprint="springer:r591795p150lj86q"}

@Article{Shaltiel02,        
  author =       {Ronen Shaltiel},
  title =        {Recent developments in extractors},
  journal =      {Bulletin of the European Association for Theoretical Computer Science},
  year =         {2002},
  url =         {http://www.wisdom.weizmann.ac.il/~ronens},
}

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

@InProceedings{CohenWi89,  
  title =        "Dispersers, Deterministic Amplification, and Weak
                 Random Sources",
  author =       "Aviad Cohen and Avi Wigderson",
  pages =        "14--19",
booktitle = {Proc. 30th FOCS},
publisher = {IEEE Computer Society Press},
year = {1989},
}

@InProceedings{ImZu,      
    author = "Russell Impagliazzo and David Zuckerman",
    title = "How to Recycle Random Bits",
    pages = "248--253",
    year = "1989",
    booktitle = {Proc.\ $30$th FOCS},
    publisher = {IEEE},
}

@article{Raghavan88,         
 author = {Prabhakar Raghavan},
 title = {Probabilistic construction of deterministic algorithms: {A}pproximating packing integer programs},
 journal = jcss,
 volume = {37},
 number = {2},
 year = {1988},
 issn = {0022-0000},
 pages = {130--143},
 eprint="jcss:10.1016/0022-0000(88)90003-7"
}

@article{HLW06,     
 author = "Shlomo Hoory and Nathan Linial and Avi Wigderson",
 title = {Expander Graphs and their Applications},
 journal = {Bull. Amer. Math. Soc.},
 volume = {43},
 pages = {439--561},
 publisher = {AMS},
 year = {2006},
 url="http://www.ams.org/bull/2006-43-04/S0273-0979-06-01126-8/"
} 

@article{GW95,   
 author = {M. X. Goemans and D. P. Williams},
 title = {Improved approximation algorithms for Max-Cut and Satisfiability Problems using Semidefinite Programming},
 journal = jacm,
 year = {1995},
 volume = {42},
 number=6,
 pages = {1115--1145},
 eprint="jacm:10.1145/227683.227684"
}

@inproceedings{ARV04,   
 author = {Sanjeev Arora and Satish Rao and Umesh Vazirani},
 title = {Expander flows, geometric embeddings, and graph partitionings},
 pages = {222--231},
 year = {2004},
 publisher = {ACM Press},
 booktitle = {Proc. 36th STOC},
 eprint="stoc:10.1145/1007352.1007355"
}

@article{ feige98threshold,   
    author = "Uriel Feige",
    title = "A Threshold of $\ln  n$  for Approximating Set Cover",
    journal = jacm,
    volume = "45",
    number = "4",
    pages = "634--652",
    year = "1998",
    url = "citeseer.ist.psu.edu/feige95threshold.html",
    eprint="jacm:10.1145/285055.285059"}

@book{ SpencerLectures,         
  author = {Joel Spencer},
  title = {Ten Lectures on the Probabilistic Method, 2nd Edition},
  year = {1994},
  chapter = {4},
  pages = {29--36},
  publisher = {SIAM}
}

@article{KolYoung05,       
  author = {Stavros G. Kolliopoulos and Neal E. Young},
  title = {Approximation algorithms for covering/packing integer programs},
  journal = jcss,
  volume = {71},
  number = {4},
  year = {2005},
  issn = {0022-0000},
  pages = {495--505},
  publisher = {Academic Press, Inc.},
  eprint="jcss:10.1016/j.jcss.2005.05.002"
}


@inproceedings{WX05,      
 author = {Avi Wigderson and David Xiao},
 title = {A randomness-efficient sampler for matrix-valued functions and applications},
 booktitle = {Proc.\ $46$th FOCS},
 year={2005},
pages="397--406",
eprint="focs:10.1109/SFCS.2005.8"
}

@misc{WXECCC,             
 author = {Avi Wigderson and David Xiao},
 title = {A randomness-efficient sampler for matrix-valued functions and applications},
 howpublished = {ECCC Report TR05-107},
 year = {2005},
 eprint="eccc:TR05-107"
}

@inproceedings{ArKa07,  
 author = {Sanjeev Arora and Satyen Kale},
 title = {A combinatorial, primal-dual approach to semidefinite programs},
 booktitle = {Proc. 39th STOC},
 year = {2007},
 isbn = {978-1-59593-631-8},
 pages = {227--236},
 location = {San Diego, California, USA},
 publisher = {ACM},
 address = {New York, NY, USA},
 eprint="stoc:10.1145/1250790.1250823"
 }

@book{GolubLoan,    
 author = {G. H. Golub and C. F. Van Loan},
 title = {Matrix Computations},
 publisher = {Johns Hopkins University Press},
 year = {1989}
}