@string{webstart = {\begin{tt}}} @string{webmid = {\linebreak[0]}} @string{til = {\~\,$\!$}} @string{webend = {\end{tt}}} @string{jacm = {Journal of the ACM}} @string{sicomp = {SIAM Journal on Computing}} @string{jcss = {Journal of Computer and System Sciences}} @string{focs97 ="Proceedings of the 38th IEEE Symposium on Foundations of Computer Science"} @string{structures90={Proceedings of the 5th IEEE Conference on Structure in Complexity Theory}} @string{structures95={Proceedings of the 10th IEEE Conference on Structure in Complexity Theory}} @string{focs04 ="Proceedings of the 45th IEEE Symposium on Foundations of Computer Science"} @string{focs05 ="Proceedings of the 46th IEEE Symposium on Foundations of Computer Science"} @string{stoc05 ="Proceedings of the 37th ACM Symposium on Theory of Computing"} @string{stoc06 ="Proceedings of the 38th ACM Symposium on Theory of Computing"} @string{stoc99 ="Proceedings of the 31st ACM Symposium on Theory of Computing"} @MISC{Tao12, author = {Terence Tao}, title = {Expansion in Finite Groups of {L}ie Type}, howpublished = {Lecture Notes}, year = {2012}, OPTmonth = {}, note = {http://www.math.ucla.edu/~tao/254b.1.12w/}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @INPROCEEDINGS{TrevisanTuVa09, AUTHOR = {Luca Trevisan and Madhur Tulsiani and Salil Vadhan}, TITLE = {Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution}, BOOKTITLE = "Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC `09)", YEAR = "2009", OPTeditor = "", OPTvolume = "", OPTnumber = "", OPTseries = "", pages = "126--136", c-address = "Paris, France", month = "15--18 July", OPTorganization = "", OPTpublisher = "", note = "Preliminary version posted as {\em ECCC} TR08-103.", OPTabstract = "", OPTkeywords = "", OPTharvard-addendum = {yes}, OPTgrants = {Miller, Guggenheim, US-Israel Binational Science Foundation grant 2006060, ONR grant N00014-04-1-0478}, file = F } @incollection {BarakShWi03, AUTHOR = {Barak, Boaz and Shaltiel, Ronen and Wigderson, Avi}, TITLE = {Computational analogues of entropy}, BOOKTITLE = {Approximation, randomization, and combinatorial optimization}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {2764}, PAGES = {200--215}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2003}, MRCLASS = {68P30 (68Q15 94A17)}, MRNUMBER = {2080793 (2005c:68042)}, DOI = {10.1007/978-3-540-45198-3_18}, URL = {http://dx.doi.org/10.1007/978-3-540-45198-3_18}, } @incollection {Trevisan11, AUTHOR = {Trevisan, Luca}, TITLE = {Dense model theorems and their applications}, BOOKTITLE = {Theory of cryptography}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6597}, PAGES = {55--57}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {11B05 (68P25 94A60)}, MRNUMBER = {2811333}, DOI = {10.1007/978-3-642-19571-6_4}, URL = {http://dx.doi.org/10.1007/978-3-642-19571-6_4}, } @incollection {LeeLuTs11, AUTHOR = {Lee, Chia-Jung and Lu, Chi-Jen and Tsai, Shi-Chun}, TITLE = {Computational randomness from generalized hardcore sets}, BOOKTITLE = {Fundamentals of computation theory}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6914}, PAGES = {78--89}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {68Q15 (06E30)}, MRNUMBER = {2886896}, DOI = {10.1007/978-3-642-22953-4_7}, URL = {http://dx.doi.org/10.1007/978-3-642-22953-4_7}, } @article {LuTsWu11, AUTHOR = {Lu, Chi-Jen and Tsai, Shi-Chun and Wu, Hsin-Lung}, TITLE = {Complexity of hard-core set proofs}, JOURNAL = {Computational Complexity}, VOLUME = {20}, YEAR = {2011}, NUMBER = {1}, PAGES = {145--171}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q17 (68Q10)}, MRNUMBER = {2796060 (2012i:68090)}, DOI = {10.1007/s00037-011-0003-7}, URL = {http://dx.doi.org/10.1007/s00037-011-0003-7}, } @incollection {ChungKaLiRa11, AUTHOR = {Chung, Kai-Min and Kalai, Yael Tauman and Liu, Feng-Hao and Raz, Ran}, TITLE = {Memory delegation}, BOOKTITLE = {Advances in cryptology---{CRYPTO} 2011}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6841}, PAGES = {151--168}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {68M07}, MRNUMBER = {2874868}, DOI = {10.1007/978-3-642-22792-9_9}, URL = {http://dx.doi.org/10.1007/978-3-642-22792-9_9}, } @inproceedings{FullerONRe12, author = {Benjamin Fuller and Adam {O'N}eill and Leonid Reyzin}, title = {A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy}, booktitle = {TCC}, year = {2012}, pages = {582-599}, ee = {http://dx.doi.org/10.1007/978-3-642-28914-9_33}, crossref = {DBLP:conf/tcc/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/tcc/2012, editor = {Ronald Cramer}, title = {Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings}, booktitle = {TCC}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {7194}, year = {2012}, isbn = {978-3-642-28913-2}, ee = {http://dx.doi.org/10.1007/978-3-642-28914-9}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{DziembowskiPi08, author = {Stefan Dziembowski and Krzysztof Pietrzak}, title = {Leakage-Resilient Cryptography}, booktitle = {FOCS}, year = {2008}, pages = {293-302}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2008.56}, crossref = {DBLP:conf/focs/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2008, title = {49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @INPROCEEDINGS{ReingoldTrTuVa08, AUTHOR = "Omer Reingold and Luca Trevisan and Madhur Tulsiani and Salil Vadhan", TITLE = "Dense Subsets of Pseudorandom Sets", BOOKTITLE = {Proceedings of the 49th Annual {IEEE} Symposium on Foundations of Computer Science (FOCS `08)}, YEAR = {2008}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, pages = {76--85}, c-address = {Philadelphia}, month = {26--28 October}, organization = {IEEE}, OPTpublisher = {}, OPTnote = {Preliminary version posted as {\em ECCC} TR08-045}, OPTabstract = {}, OPTkeywords = {}, } @inproceedings {BarakHaKa09, AUTHOR = {Barak, Boaz and Hardt, Moritz and Kale, Satyen}, TITLE = {The uniform hardcore lemma via approximate {B}regman projections}, BOOKTITLE = {Proceedings of the {T}wentieth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms}, PAGES = {1193--1200}, PUBLISHER = {SIAM}, ADDRESS = {Philadelphia, PA}, YEAR = {2009}, MRCLASS = {68Q15 (68T05 94A60)}, MRNUMBER = {2807562}, } @incollection {Holenstein05, AUTHOR = {Holenstein, Thomas}, TITLE = {Key agreement from weak bit agreement}, BOOKTITLE = {S{TOC}'05: {P}roceedings of the 37th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {664--673}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2005}, MRCLASS = {94A60 (68M12)}, MRNUMBER = {2181671 (2006g:94023)}, DOI = {10.1145/1060590.1060689}, URL = {http://dx.doi.org/10.1145/1060590.1060689}, } @article{KlivansSe03, author = {Adam R. Klivans and Rocco A. Servedio}, title = {Boosting and Hard-Core Set Construction}, journal = {Machine Learning}, volume = {51}, number = {3}, year = {2003}, pages = {217-238}, ee = {http://dx.doi.org/10.1023/A:1022949332276}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{BureshOppenheimKaSa06, author = {Joshua Buresh-Oppenheim and Valentine Kabanets and Rahul Santhanam}, title = {Uniform Hardness Amplification in NP via Monotone Codes}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {13}, number = {154}, year = {2006}, ee = {http://eccc.hpi-web.de/eccc-reports/2006/TR06-154/index.html}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {Williams10, AUTHOR = {Williams, Ryan}, TITLE = {Improving exhaustive search implies superpolynomial lower bounds}, BOOKTITLE = {S{TOC}'10---{P}roceedings of the 2010 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing}, PAGES = {231--240}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2010}, MRCLASS = {68Q17}, MRNUMBER = {2743271 (2011i:68049)}, } @inproceedings{Williams11, author = {Ryan Williams}, title = {Non-uniform ACC Circuit Lower Bounds}, booktitle = {IEEE Conference on Computational Complexity}, year = {2011}, pages = {115-125}, ee = {http://dx.doi.org/10.1109/CCC.2011.36}, crossref = {DBLP:conf/coco/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2011, title = {Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{SimaZa11, author = {Jir\'{\i} S\'{\i}ma and Stanislav Z{\'a}k}, title = {Almost {\it k}-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs}, booktitle = {CSR}, year = {2011}, pages = {120-133}, ee = {http://dx.doi.org/10.1007/978-3-642-20712-9_10}, crossref = {DBLP:conf/csr/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/csr/2011, editor = {Alexander S. Kulikov and Nikolay K. Vereshchagin}, title = {Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings}, booktitle = {CSR}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {6651}, year = {2011}, isbn = {978-3-642-20711-2}, ee = {http://dx.doi.org/10.1007/978-3-642-20712-9}, bibsource = {DBLP, http://dblp.uni-trier.de} } @book {Terras99, AUTHOR = {Terras, Audrey}, TITLE = {Fourier analysis on finite groups and applications}, SERIES = {London Mathematical Society Student Texts}, VOLUME = {43}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {1999}, PAGES = {x+442}, ISBN = {0-521-45718-1}, MRCLASS = {11-02 (11T60 11Z05 20C15 43-01)}, MRNUMBER = {1695775 (2000d:11003)}, MRREVIEWER = {Stefan K{\"u}hnlein}, DOI = {10.1017/CBO9780511626265}, URL = {http://dx.doi.org/10.1017/CBO9780511626265}, } @inproceedings{GopalanMeRe12, author = {Parikshit Gopalan and Raghu Meka and Omer Reingold}, title = {{DNF} Sparsification and a Faster Deterministic Counting Algorithm}, booktitle = {IEEE Conference on Computational Complexity}, year = {2012}, pages = {126-135}, ee = {http://doi.ieeecomputersociety.org/10.1109/CCC.2012.38}, crossref = {DBLP:conf/coco/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2012, title = {Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE}, year = {2012}, isbn = {978-1-4673-1663-7}, ee = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6242817}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Goldreich07-ppsprimer, AUTHOR = {Goldreich, Oded}, TITLE = {Probabilistic proof systems: a primer}, JOURNAL = {Foundations and Trends${}^\circledR$ in Theoretical Computer Science}, VOLUME = {3}, YEAR = {2007}, NUMBER = {1}, PAGES = {1--91 (2008)}, ISSN = {1551-305X}, ISBN = {978-1-60198-152-3}, MRCLASS = {68T15 (68T20)}, MRNUMBER = {2443191 (2010a:68144)}, DOI = {10.1561/0400000023}, URL = {http://dx.doi.org/10.1561/0400000023}, } @inproceedings{Smolensky87, author = {Roman Smolensky}, title = {Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity}, booktitle = {STOC}, year = {1987}, pages = {77-82}, ee = {http://doi.acm.org/10.1145/28395.28404}, crossref = {DBLP:conf/stoc/STOC19}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC19, editor = {Alfred V. Aho}, title = {Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1987}, isbn = {0-89791-221-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Razborov87, AUTHOR = {Razborov, A. A.}, TITLE = {Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function}, JOURNAL = {Akademiya Nauk SSSR. Matematicheskie Zametki}, VOLUME = {41}, YEAR = {1987}, NUMBER = {4}, PAGES = {598--607, 623}, ISSN = {0025-567X}, MRCLASS = {03G05 (68Q15 94C10)}, MRNUMBER = {897705 (89h:03110)}, MRREVIEWER = {Koriolan Gilezan}, } @ARTICLE{RazReVa02, author = {Ran Raz and Omer Reingold and Salil Vadhan}, title = {Extracting all the Randomness and Reducing the Error in {Trevisan's} Extractors}, journal = {Journal of Computer and System Sciences}, year = {2002}, volume = {65}, number = {1}, pages = {97--128}, month = {August}, OPTnote = {Special Issue on STOC `99}, OPTkey = {}, OPTcrossref = {}, OPTannote = {}, } @UNPUBLISHED{ImpagliazzoWi96, author = {Russell Impagliazzo and Avi Wigderson}, title = {An information-theoretic variant of the inclusion- exclusion bound (preliminary version)}, year = {1996}, note = {Unpublished manuscript} } @techreport{Steinke12, author = {Thomas Steinke}, title = {Pseudorandomness for Permutation Branching Programs Without the Group Theory}, institution = {Electronic Colloquium on Computational Complexity (ECCC)}, year = {2012}, number = {TR12-083}, month = {July}, url = {http://eccc.hpi-web.de/report/2012/083/}, OPTgrants = {NSF grant CCF-1116616 and Lord Rutherford Memorial Research Fellowship} } @inproceedings{De11, author = {Anindya De}, title = {Pseudorandomness for Permutation and Regular Branching Programs}, booktitle = {IEEE Conference on Computational Complexity}, year = {2011}, pages = {221-231}, ee = {http://dx.doi.org/10.1109/CCC.2011.23}, crossref = {DBLP:conf/coco/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2011, title = {Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{KouckyNiPu11, author = {Michal Kouck{\'y} and Prajakta Nimbhorkar and Pavel Pudl{\'a}k}, title = {Pseudorandom generators for group products: extended abstract}, booktitle = {STOC}, year = {2011}, pages = {263-272}, ee = {http://doi.acm.org/10.1145/1993636.1993672}, crossref = {DBLP:conf/stoc/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/2011, editor = {Lance Fortnow and Salil P. Vadhan}, title = {Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011}, booktitle = {STOC}, publisher = {ACM}, year = {2011}, isbn = {978-1-4503-0691-1}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{Guruswami11, author = {Venkatesan Guruswami}, title = {Linear-Algebraic List Decoding of Folded Reed-Solomon Codes}, booktitle = {IEEE Conference on Computational Complexity}, year = {2011}, pages = {77-85}, ee = {http://dx.doi.org/10.1109/CCC.2011.22}, crossref = {DBLP:conf/coco/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{DvirLo12, author = {Zeev Dvir and Shachar Lovett}, title = {Subspace evasive sets}, booktitle = {STOC}, year = {2012}, pages = {351-358}, ee = {http://doi.acm.org/10.1145/2213977.2214010}, crossref = {DBLP:conf/stoc/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2011, title = {Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{GuruswamiXi12, author = {Venkatesan Guruswami and Chaoping Xing}, title = {Folded codes from function field towers and improved optimal rate list decoding}, booktitle = {STOC}, year = {2012}, pages = {339-350}, ee = {http://doi.acm.org/10.1145/2213977.2214009}, crossref = {DBLP:conf/stoc/2012}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/2012, editor = {Howard J. Karloff and Toniann Pitassi}, title = {Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}, booktitle = {STOC}, publisher = {ACM}, year = {2012}, isbn = {978-1-4503-1245-5}, ee = {http://dl.acm.org/citation.cfm?id=2213977}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {ShpilkaYe09, AUTHOR = {Shpilka, Amir and Yehudayoff, Amir}, TITLE = {Arithmetic circuits: a survey of recent results and open questions}, JOURNAL = {Foundations and Trends${}^\circledR$ in Theoretical Computer Science}, VOLUME = {5}, YEAR = {2009}, NUMBER = {3-4}, PAGES = {207--388 (2010)}, ISSN = {1551-305X}, ISBN = {978-1-60198-400-5; 978-1-60198-401-2}, MRCLASS = {68Q15 (68Q17 68W30)}, MRNUMBER = {2756166 (2011m:68089)}, DOI = {10.1561/0400000039}, URL = {http://dx.doi.org/10.1561/0400000039}, } @incollection {Tessaro11, AUTHOR = {Tessaro, Stefano}, TITLE = {Security amplification for the cascade of arbitrarily weak {PRP}s: tight bounds via the interactive hardcore lemma}, BOOKTITLE = {Theory of cryptography}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6597}, PAGES = {37--54}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {94A60 (68P25 68P30)}, MRNUMBER = {2811332}, MRREVIEWER = {Adrian C. Atanasiu}, DOI = {10.1007/978-3-642-19571-6_3}, URL = {http://dx.doi.org/10.1007/978-3-642-19571-6_3}, } @PHDTHESIS{Tessaro10, author = {Stefano Tessaro}, title = {Computational Indistinguishability Amplification}, school = {ETH Zurich}, year = {2010}, OPTtype = {}, OPTaddress = {}, OPTmonth = {}, note = {http://e-collection.library.ethz.ch/eserv/eth:1817/eth-1817-02.pdf}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @PHDTHESIS{Chung11, author = {Kai-Min Chung}, title = {Efficient Parallel Repetition Theorems with Applications to Security Amplification}, school = {Harvard University}, year = {2011}, OPTtype = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @incollection {DodisImJaKa09, AUTHOR = {Dodis, Yevgeniy and Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine}, TITLE = {Security amplification for {\it interactive} cryptographic primitives}, BOOKTITLE = {Theory of cryptography}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {5444}, PAGES = {128--145}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2009}, MRCLASS = {94A60}, MRNUMBER = {2546195 (2011a:94064)}, DOI = {10.1007/978-3-642-00457-5_9}, URL = {http://dx.doi.org/10.1007/978-3-642-00457-5_9}, } @article {ImpagliazzoJaKaWi09, AUTHOR = {Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine and Wigderson, Avi}, TITLE = {Uniform direct product theorems: simplified, optimized, and derandomized}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {39}, YEAR = {2009/10}, NUMBER = {4}, PAGES = {1637--1665}, ISSN = {0097-5397}, MRCLASS = {68Q15 (68P30 68Q17 68Q25)}, MRNUMBER = {2580543 (2011g:68089)}, MRREVIEWER = {Frederic Green}, DOI = {10.1137/080734030}, URL = {http://dx.doi.org/10.1137/080734030}, } @article {ImpagliazzoJaKa09, AUTHOR = {Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine}, TITLE = {Approximate list-decoding of direct product codes and uniform hardness amplification}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {39}, YEAR = {2009}, NUMBER = {2}, PAGES = {564--605}, ISSN = {0097-5397}, MRCLASS = {68Q17 (68P30 68Q25 68W20 94B35)}, MRNUMBER = {2529772 (2011b:68070)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1137/070683994}, URL = {http://dx.doi.org/10.1137/070683994}, } @inproceedings {Impagliazzo02, AUTHOR = {Impagliazzo, Russell}, TITLE = {Hardness as randomness: a survey of universal derandomization}, BOOKTITLE = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. {III} ({B}eijing, 2002)}, PAGES = {659--672}, PUBLISHER = {Higher Ed. Press}, ADDRESS = {Beijing}, YEAR = {2002}, MRCLASS = {68Q15 (68Q10 68Q17 68W20)}, MRNUMBER = {1957568 (2004a:68030)}, } @incollection {Trevisan05, AUTHOR = {Trevisan, Luca}, TITLE = {On uniform amplification of hardness in {NP}}, BOOKTITLE = {S{TOC}'05: {P}roceedings of the 37th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {31--38}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2005}, MRCLASS = {68Q15}, MRNUMBER = {2181599 (2006g:68078)}, DOI = {10.1145/1060590.1060595}, URL = {http://dx.doi.org/10.1145/1060590.1060595}, } @MISC{ODonnell12, AUTHOR = {{O'D}onnell, Ryan}, title = {Analysis of Boolean Functions}, howpublished = {Book draft available at \texttt{analysisofbooleanfunctions.org}}, year = {2012}, OPTmonth = {}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @article {LuTsWu07, AUTHOR = {Lu, Chi-Jen and Tsai, Shi-Chun and Wu, Hsin-Lung}, TITLE = {Improved hardness amplification in {NP}}, JOURNAL = {Theoretical Computer Science}, VOLUME = {370}, YEAR = {2007}, NUMBER = {1-3}, PAGES = {293--298}, ISSN = {0304-3975}, CODEN = {TCSDI}, MRCLASS = {68Q15}, MRNUMBER = {2294595 (2007k:68035)}, DOI = {10.1016/j.tcs.2006.10.009}, URL = {http://dx.doi.org/10.1016/j.tcs.2006.10.009}, } @article {HealyVaVi06, AUTHOR = {Healy, Alexander and Vadhan, Salil and Viola, Emanuele}, TITLE = {Using nondeterminism to amplify hardness}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {35}, YEAR = {2006}, NUMBER = {4}, PAGES = {903--931 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q17}, MRNUMBER = {2203732 (2006j:68033)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1137/S0097539705447281}, URL = {http://dx.doi.org/10.1137/S0097539705447281}, } @article {ODonnell04, AUTHOR = {{O'D}onnell, Ryan}, TITLE = {Hardness amplification within {NP}}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {69}, YEAR = {2004}, NUMBER = {1}, PAGES = {68--94}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15}, MRNUMBER = {2070800 (2005f:68045)}, MRREVIEWER = {Christoph Meinel}, DOI = {10.1016/j.jcss.2004.01.001}, URL = {http://dx.doi.org/10.1016/j.jcss.2004.01.001}, } @article {AzarMoNa98, AUTHOR = {Azar, Yossi and Motwani, Rajeev and Naor, Joseph}, TITLE = {Approximating probability distributions using small sample spaces}, JOURNAL = {Combinatorica}, VOLUME = {18}, YEAR = {1998}, NUMBER = {2}, PAGES = {151--171}, ISSN = {0209-9683}, MRCLASS = {68Q25 (60C05 60E15)}, MRNUMBER = {1656537 (2000k:68064)}, DOI = {10.1007/PL00009813}, URL = {http://dx.doi.org/10.1007/PL00009813}, } @article {AlonMa95, AUTHOR = {Alon, Noga and Mansour, Yishay}, TITLE = {{$\epsilon$}-discrepancy sets and their application for interpolation of sparse polynomials}, JOURNAL = {Inform. Process. Lett.}, FJOURNAL = {Information Processing Letters}, VOLUME = {54}, YEAR = {1995}, NUMBER = {6}, PAGES = {337--342}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {11K31 (11K38 11Y16 65D05)}, MRNUMBER = {1336714 (96g:11094)}, MRREVIEWER = {Robert F. Tichy}, DOI = {10.1016/0020-0190(95)00032-8}, URL = {http://dx.doi.org/10.1016/0020-0190(95)00032-8}, } @article {Katz89, AUTHOR = {Katz, Nicholas M.}, TITLE = {An estimate for character sums}, JOURNAL = {Journal of the American Mathematical Society}, VOLUME = {2}, YEAR = {1989}, NUMBER = {2}, PAGES = {197--200}, ISSN = {0894-0347}, MRCLASS = {11L15 (11L40 11T21 12E20)}, MRNUMBER = {965007 (90b:11081)}, MRREVIEWER = {Yurey A. Drakokhrust}, DOI = {10.2307/1990974}, URL = {http://dx.doi.org/10.2307/1990974}, } @article {AjtaiIwKoPiSz90, AUTHOR = {Ajtai, Mikl{\'o}s and Iwaniec, Henryk and Koml{\'o}s, J{\'a}nos and Pintz, J{\'a}nos and Szemer{\'e}di, Endre}, TITLE = {Construction of a thin set with small {F}ourier coefficients}, JOURNAL = {Bull. London Math. Soc.}, FJOURNAL = {The Bulletin of the London Mathematical Society}, VOLUME = {22}, YEAR = {1990}, NUMBER = {6}, PAGES = {583--590}, ISSN = {0024-6093}, CODEN = {LMSBBT}, MRCLASS = {11B05 (05B10 11B75 11Y16 68R10)}, MRNUMBER = {1099009 (92e:11010)}, MRREVIEWER = {Rita Giuliano Antonini}, DOI = {10.1112/blms/22.6.583}, URL = {http://dx.doi.org/10.1112/blms/22.6.583}, } @article {RazborovSzWi93, AUTHOR = {Razborov, A. and Szemer{\'e}di, E. and Wigderson, A.}, TITLE = {Constructing small sets that are uniform in arithmetic progressions}, JOURNAL = {Combin. Probab. Comput.}, FJOURNAL = {Combinatorics, Probability and Computing}, VOLUME = {2}, YEAR = {1993}, NUMBER = {4}, PAGES = {513--518}, ISSN = {0963-5483}, MRCLASS = {11K38}, MRNUMBER = {1264723 (94k:11086)}, MRREVIEWER = {Robert F. Tichy}, DOI = {10.1017/S0963548300000870}, URL = {http://dx.doi.org/10.1017/S0963548300000870}, } @article {Klawe84, AUTHOR = {Klawe, Maria}, TITLE = {Limitations on explicit constructions of expanding graphs}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {13}, YEAR = {1984}, NUMBER = {1}, PAGES = {156--166}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68R10 (05C99)}, MRNUMBER = {731033 (85k:68077)}, DOI = {10.1137/0213011}, URL = {http://dx.doi.org/10.1137/0213011}, } @article{deWolf08, author = {Ronald de Wolf}, title = {A Brief Introduction to Fourier Analysis on the Boolean Cube}, journal = {Theory of Computing, Graduate Surveys}, volume = {1}, year = {2008}, pages = {1-20}, ee = {http://dx.doi.org/10.4086/toc.gs.2008.001}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {BenSassonGoHaSuVa06, AUTHOR = {Ben-Sasson, Eli and Goldreich, Oded and Harsha, Prahladh and Sudan, Madhu and Vadhan, Salil}, TITLE = {Robust {PCP}s of proximity, shorter {PCP}s and applications to coding}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2006}, NUMBER = {4}, PAGES = {889--974}, ISSN = {0097-5397}, MRCLASS = {68Q17 (68P30 94B60)}, MRNUMBER = {2272268 (2008b:68039)}, MRREVIEWER = {Johan H{\aa}stad}, DOI = {10.1137/S0097539705446810}, URL = {http://dx.doi.org/10.1137/S0097539705446810}, } @inproceedings {BenSassonSuVaWi03, AUTHOR = {Ben-Sasson, Eli and Sudan, Madhu and Vadhan, Salil and Wigderson, Avi}, TITLE = {Randomness-efficient low degree tests and short {PCP}s via epsilon-biased sets}, BOOKTITLE = {Proceedings of the {T}hirty-{F}ifth {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {612--621 (electronic)}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2003}, MRCLASS = {68Q15 (94A60)}, MRNUMBER = {2120440 (2005k:68058)}, DOI = {10.1145/780542.780631}, URL = {http://dx.doi.org/10.1145/780542.780631}, } @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 = {1164842 (93k:94006a)}, DOI = {10.1002/rsa.3240030308}, URL = {http://dx.doi.org/10.1002/rsa.3240030308}, NOTE = {See also addendum in issue 4(1), 1993, pp. 199--120} } @article {AlonGoHaPe92-addendum, AUTHOR = {Alon, N. and Goldreich, O. and H{\aa}stad, J. and Peralta, R.}, TITLE = {Addendum to: ``{S}imple constructions of almost {$k$}-wise independent random variables''}, JOURNAL = {Random Structures \& Algorithms}, VOLUME = {4}, YEAR = {1993}, NUMBER = {1}, PAGES = {119--120}, ISSN = {1042-9832}, MRCLASS = {94A55 (65C10 68Q30)}, MRNUMBER = {1192531 (93k:94006b)}, DOI = {10.1002/rsa.3240040109}, URL = {http://dx.doi.org/10.1002/rsa.3240040109}, } @inproceedings{Dvir09, author = {Zeev Dvir}, title = {Extractors for Varieties}, booktitle = {IEEE Conference on Computational Complexity}, year = {2009}, pages = {102-113}, ee = {http://doi.ieeecomputersociety.org/10.1109/CCC.2009.7}, crossref = {DBLP:conf/coco/2009}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2009, title = {Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2009}, isbn = {978-0-7695-3717-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {GabizonRa08, AUTHOR = {Gabizon, Ariel and Raz, Ran}, TITLE = {Deterministic extractors for affine sources over large fields}, JOURNAL = {Combinatorica}, VOLUME = {28}, YEAR = {2008}, NUMBER = {4}, PAGES = {415--440}, ISSN = {0209-9683}, MRCLASS = {05D10 (11T24)}, MRNUMBER = {2452843 (2009m:05188)}, DOI = {10.1007/s00493-008-2259-3}, URL = {http://dx.doi.org/10.1007/s00493-008-2259-3}, } @article {DvirGaWi09, AUTHOR = {Dvir, Zeev and Gabizon, Ariel and Wigderson, Avi}, TITLE = {Extractors and rank extractors for polynomial sources}, JOURNAL = {Computational Complexity}, VOLUME = {18}, YEAR = {2009}, NUMBER = {1}, PAGES = {1--58}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68W20}, MRNUMBER = {2505192 (2010b:68174)}, MRREVIEWER = {Domingos Dellamonica, Jr.}, DOI = {10.1007/s00037-009-0258-4}, URL = {http://dx.doi.org/10.1007/s00037-009-0258-4}, } @inproceedings{BenSassonZe11, author = {Eli {Ben-S}asson and Noga Zewi}, title = {From affine to two-source extractors via approximate duality}, booktitle = {STOC}, year = {2011}, pages = {177-186}, ee = {http://doi.acm.org/10.1145/1993636.1993661}, crossref = {DBLP:conf/stoc/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/2011, editor = {Lance Fortnow and Salil P. Vadhan}, title = {Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011}, booktitle = {STOC}, publisher = {ACM}, year = {2011}, isbn = {978-1-4503-0691-1}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {BenSassonKo09, AUTHOR = {{Ben-S}asson, Eli and Kopparty, Swastik}, TITLE = {Affine dispersers from subspace polynomials}, BOOKTITLE = {S{TOC}'09---{P}roceedings of the 2009 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing}, PAGES = {65--74}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2009}, MRCLASS = {68Q87 (65C10)}, MRNUMBER = {2780051 (2012g:68168)}, } @inproceedings{Li11, author = {Xin Li}, title = {A New Approach to Affine Extractors and Dispersers}, booktitle = {IEEE Conference on Computational Complexity}, year = {2011}, pages = {137-147}, ee = {http://dx.doi.org/10.1109/CCC.2011.27}, crossref = {DBLP:conf/coco/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2011, title = {Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, June 8-10, 2011}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Bourgain07, AUTHOR = {Bourgain, Jean}, TITLE = {On the construction of affine extractors}, JOURNAL = {Geometric and Functional Analysis}, VOLUME = {17}, YEAR = {2007}, NUMBER = {1}, PAGES = {33--57}, ISSN = {1016-443X}, CODEN = {GFANFB}, MRCLASS = {68R10 (11L07 60C05 68W20)}, MRNUMBER = {2306652 (2008b:68085)}, MRREVIEWER = {Alessandro Conflitti}, DOI = {10.1007/s00039-007-0593-z}, URL = {http://dx.doi.org/10.1007/s00039-007-0593-z}, } @INPROCEEDINGS{KonigMa04, author = {Robert K{\"o}nig and Ueli M. Maurer}, title = {Extracting randomness from generalized symbol-fixing and Markov sources}, booktitle = {Proceedings of 2004 IEEE International Symposium on Information Theory}, year = {2004}, pages = {232} } @inproceedings{KonigMa05, author = {Robert K{\"o}nig and Ueli M. Maurer}, title = {Generalized Strong Extractors and Deterministic Privacy Amplification}, booktitle = {IMA Int. Conf.}, year = {2005}, pages = {322-339}, ee = {http://dx.doi.org/10.1007/11586821_22}, crossref = {DBLP:conf/ima/2005}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/ima/2005, editor = {Nigel P. Smart}, title = {Cryptography and Coding, 10th IMA International Conference, Cirencester, UK, December 19-21, 2005, Proceedings}, booktitle = {IMA Int. Conf.}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {3796}, year = {2005}, isbn = {3-540-30276-X}, bibsource = {DBLP, http://dblp.uni-trier.de} } @MISC{PrincetonAdditiveCombinatorics07, author = {Boaz Barak and Luca Trevisan and Avi Wigderson}, title = {Additive Combinatorics and Computer Science}, howpublished = {\texttt{http://www.cs.princeton.edu/theory/index.php/Main/AdditiveCombinatoricsMinicourse}}, year = {2007}, month = {August} } @InProceedings{TrevisanVa00, author = {Luca Trevisan and Salil Vadhan}, title = {Extracting Randomness from Samplable Distributions}, booktitle = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS `00)}, OPTcrossref = {}, OPTkey = {}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, year = 2000, organization = {IEEE}, OPTpublisher = {}, address = {Redondo Beach, CA}, month = {17--19 } # oct, pages = {32--42}, OPTnote = {}, OPTannote = {} } @INPROCEEDINGS{DodisRiVa12, AUTHOR = {Yevgeniy Dodis and Thomas Ristenpart and Salil Vadhan}, TITLE = {Randomness Condensers for Efficiently Samplable, Seed-Dependent Sources}, BOOKTITLE = {Proceedings of the 9th IACR Theory of Cryptography Conference (TCC `12)}, YEAR = {2012}, editor = {Ronald Cramer}, volume = {7194}, OPTnumber = {}, series = {Lecture Notes on Computer Science}, pages = {618-635}, c-address = {Taormina, Italy}, month = {19--21 March}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {To appear}, OPTabstract = {}, OPTkeywords = {}, OPTgrants = {NSF grant CCF-1116616, MSR-SVC, Stanford}, OPTharvard-addendum = {yes} } @article {Viola12, AUTHOR = {Viola, Emanuele}, TITLE = {The complexity of distributions}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {41}, YEAR = {2012}, NUMBER = {1}, PAGES = {191--218}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68Q17 (68P05 68Q87)}, MRNUMBER = {2888326}, DOI = {10.1137/100814998}, URL = {http://dx.doi.org/10.1137/100814998}, } @inproceedings{Viola11, author = {Emanuele Viola}, title = {Extractors for Circuit Sources}, booktitle = {FOCS}, year = {2011}, pages = {220-229}, ee = {http://dx.doi.org/10.1109/FOCS.2011.20}, crossref = {DBLP:conf/focs/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2011, editor = {Rafail Ostrovsky}, title = {IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011}, booktitle = {FOCS}, publisher = {IEEE}, year = {2011}, isbn = {978-1-4577-1843-4}, ee = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {DeWa11, AUTHOR = {De, Anindya and Watson, Thomas}, TITLE = {Extractors and lower bounds for locally samplable sources}, BOOKTITLE = {Approximation, randomization, and combinatorial optimization}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6845}, PAGES = {483--494}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {68Q87 (68Q15)}, MRNUMBER = {2863284}, DOI = {10.1007/978-3-642-22935-0_41}, URL = {http://dx.doi.org/10.1007/978-3-642-22935-0_41}, } @article {BarakKiShSuWi10, AUTHOR = {Barak, B. and Kindler, G. and Shaltiel, R. and Sudakov, B. and Wigderson, A.}, TITLE = {Simulating independence: new constructions of condensers, {R}amsey graphs, dispersers, and extractors}, JOURNAL = {Journal of the ACM}, VOLUME = {57}, YEAR = {2010}, NUMBER = {4}, PAGES = {Art. 20, 52}, ISSN = {0004-5411}, MRCLASS = {05C85 (05C55 05D40 68Q87 68R10 68W20)}, MRNUMBER = {2677118 (2011i:05236)}, DOI = {10.1145/1734213.1734214}, URL = {http://dx.doi.org/10.1145/1734213.1734214}, } @incollection {Erdos69, AUTHOR = {Erd{\H{o}}s, P.}, TITLE = {Problems and results in chromatic graph theory}, BOOKTITLE = {Proof {T}echniques in {G}raph {T}heory ({P}roc. {S}econd {A}nn {A}rbor {G}raph {T}heory {C}onf., {A}nn {A}rbor, {M}ich., 1968)}, PAGES = {27--35}, PUBLISHER = {Academic Press}, ADDRESS = {New York}, YEAR = {1969}, MRCLASS = {05.55}, MRNUMBER = {0252273 (40 \#5494)}, MRREVIEWER = {J. W. Moon}, } @article {FranklWi81, AUTHOR = {Frankl, P. and Wilson, R. M.}, TITLE = {Intersection theorems with geometric consequences}, JOURNAL = {Combinatorica}, VOLUME = {1}, YEAR = {1981}, NUMBER = {4}, PAGES = {357--368}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05C35 (05A17 05A20 05C15)}, MRNUMBER = {647986 (84g:05085)}, MRREVIEWER = {E. C. Milner}, DOI = {10.1007/BF02579457}, URL = {http://dx.doi.org/10.1007/BF02579457}, } @article {KampRaVaZu11, AUTHOR = {Kamp, Jesse and Rao, Anup and Vadhan, Salil and Zuckerman, David}, TITLE = {Deterministic extractors for small-space sources}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {77}, YEAR = {2011}, NUMBER = {1}, PAGES = {191--220}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q87 (68W20)}, MRNUMBER = {2767133 (2012e:68253)}, DOI = {10.1016/j.jcss.2010.06.014}, URL = {http://dx.doi.org/10.1016/j.jcss.2010.06.014}, } @article {Rao09, AUTHOR = {Rao, Anup}, TITLE = {Extractors for a constant number of polynomially small min-entropy independent sources}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {39}, YEAR = {2009}, NUMBER = {1}, PAGES = {168--194}, ISSN = {0097-5397}, MRCLASS = {68Q87 (05C55 05C65)}, MRNUMBER = {2506523 (2010j:68091)}, MRREVIEWER = {Domingos Dellamonica, Jr.}, DOI = {10.1137/060671218}, URL = {http://dx.doi.org/10.1137/060671218}, } @article {BarakImWi06, AUTHOR = {Barak, Boaz and Impagliazzo, Russell and Wigderson, Avi}, TITLE = {Extracting randomness using few independent sources}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2006}, NUMBER = {4}, PAGES = {1095--1118 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q10 (05C55 68W20)}, MRNUMBER = {2272272 (2007j:68048)}, MRREVIEWER = {Heng Liang}, DOI = {10.1137/S0097539705447141}, URL = {http://dx.doi.org/10.1137/S0097539705447141}, } @article {BourgainKaTa04, AUTHOR = {Bourgain, J. and Katz, N. and Tao, T.}, TITLE = {A sum-product estimate in finite fields, and applications}, JOURNAL = {Geometric and Functional Analysis}, VOLUME = {14}, YEAR = {2004}, NUMBER = {1}, PAGES = {27--57}, ISSN = {1016-443X}, CODEN = {GFANFB}, MRCLASS = {11B75 (11T30)}, MRNUMBER = {2053599 (2005d:11028)}, MRREVIEWER = {Ben Joseph Green}, DOI = {10.1007/s00039-004-0451-1}, URL = {http://dx.doi.org/10.1007/s00039-004-0451-1}, } @book {GrahamRoSp90, AUTHOR = {Graham, Ronald L. and Rothschild, Bruce L. and Spencer, Joel H.}, TITLE = {Ramsey theory}, SERIES = {Wiley-Interscience Series in Discrete Mathematics and Optimization}, EDITION = {Second}, NOTE = {A Wiley-Interscience Publication}, PUBLISHER = {John Wiley \& Sons Inc.}, ADDRESS = {New York}, YEAR = {1990}, PAGES = {xii+196}, ISBN = {0-471-50046-1}, MRCLASS = {05-02 (04A20 05A99 05C55 54H20)}, MRNUMBER = {1044995 (90m:05003)}, } @book {KushilevitzNi97, AUTHOR = {Kushilevitz, Eyal and Nisan, Noam}, TITLE = {Communication complexity}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {1997}, PAGES = {xiv+189}, ISBN = {0-521-56067-5}, MRCLASS = {68Q15 (68-02 68Q10 68Q25 94C10)}, MRNUMBER = {1426129 (98c:68074)}, MRREVIEWER = {Juraj Hromkovi{\v{c}}}, } @inproceedings{AgrawalVi08, author = {Manindra Agrawal and V. Vinay}, title = {Arithmetic Circuits: A Chasm at Depth Four}, booktitle = {FOCS}, year = {2008}, pages = {67-75}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2008.32}, crossref = {DBLP:conf/focs/2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2008, title = {49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2008}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {BuhrmanFoTh98, AUTHOR = {Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas}, TITLE = {Nonrelativizing separations}, BOOKTITLE = {Thirteenth {A}nnual {IEEE} {C}onference on {C}omputational {C}omplexity ({B}uffalo, {NY}, 1998)}, PAGES = {8--12}, PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA}, YEAR = {1998}, MRCLASS = {68Q15}, MRNUMBER = {1655676 (99i:68043)}, DOI = {10.1109/CCC.1998.694585}, URL = {http://dx.doi.org/10.1109/CCC.1998.694585}, } @article {AydinliogluGuHiKa11, AUTHOR = {Aydinlio{\~g}lu, Bari{\c{s}} and Gutfreund, Dan and Hitchcock, John M. and Kawachi, Akinori}, TITLE = {Derandomizing {A}rthur-{M}erlin games and approximate counting implies exponential-size lower bounds}, JOURNAL = {Computational Complexity}, VOLUME = {20}, YEAR = {2011}, NUMBER = {2}, PAGES = {329--366}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q17)}, MRNUMBER = {2822874 (2012e:68094)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1007/s00037-011-0010-8}, URL = {http://dx.doi.org/10.1007/s00037-011-0010-8}, } @article{AydinliogluMe12, author = {Bari{\c{s}} Aydinlio{\~g}lu and Dieter van Melkebeek}, title = {Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {19}, year = {2012}, pages = {80}, ee = {http://eccc.hpi-web.de/report/2012/080}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {AaronsonMe11, AUTHOR = {Aaronson, Scott and van Melkebeek, Dieter}, TITLE = {On circuit lower bounds from derandomization}, JOURNAL = {Theory of Computing. An Open Access Journal}, VOLUME = {7}, YEAR = {2011}, PAGES = {177--184}, ISSN = {1557-2862}, MRCLASS = {68Q17 (68Q10 68Q15)}, MRNUMBER = {2862499}, DOI = {10.4086/toc.2011.v007a012}, URL = {http://dx.doi.org/10.4086/toc.2011.v007a012}, } @INPROCEEDINGS{GopalanMeReTrVa12, AUTHOR = {Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan}, TITLE = {Better Pseudorandom Generators via Milder Pseudorandom Restrictions}, BOOKTITLE = {Proceedings of the 53rd Annual {IEEE} Symposium on Foundations of Computer Science (FOCS `12)}, YEAR = {2012}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTpages = {}, c-address = {New Brunswick}, month = {20--23 October}, organization = {IEEE}, OPTpublisher = {}, note = {To appear}, OPTgrants ={}, OPTabstract = {}, OPTkeywords = {}, OPTharvard-addendum = {}, OPTdoi = {} } @MISC{SaksZu95, author = {Michael Saks and David Zuckerman}, title = {Unpublished manuscript}, OPTnote = {}, year = {1995}, OPTmonth = {}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @MISC{Kalai04, author = {Adam Tauman Kalai}, title = {Unpublished manuscript}, OPThowpublished = {}, year = {2004}, OPTmonth = {}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @inproceedings{BravermanRaRaYe10, author = {Mark Braverman and Anup Rao and Ran Raz and Amir Yehudayoff}, title = {Pseudorandom Generators for Regular Branching Programs}, booktitle = {FOCS}, year = {2010}, pages = {40-47}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.11}, crossref = {DBLP:conf/focs/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2010, title = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2010}, isbn = {978-0-7695-4244-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{BrodyVe10, author = {Joshua Brody and Elad Verbin}, title = {The Coin Problem and Pseudorandomness for Branching Programs}, booktitle = {FOCS}, year = {2010}, pages = {30-39}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.10}, crossref = {DBLP:conf/focs/2010}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2010, title = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2010}, isbn = {978-0-7695-4244-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{BogdanovDvVeYe09, author = {Andrej Bogdanov and Zeev Dvir and Elad Verbin and Amir Yehudayoff}, title = {Pseudorandomness for Width 2 Branching Programs}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {16}, year = {2009}, pages = {70}, ee = {http://eccc.hpi-web.de/report/2009/070}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {ArmoniSaWiZh96, AUTHOR = {Armoni, Roy and Saks, Michael and Wigderson, Avi and Zhou, Shiyu}, TITLE = {Discrepancy sets and pseudorandom generators for combinatorial rectangles}, BOOKTITLE = {37th {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience ({B}urlington, {VT}, 1996)}, PAGES = {412--421}, PUBLISHER = {IEEE Comput. Soc. Press}, ADDRESS = {Los Alamitos, CA}, YEAR = {1996}, MRCLASS = {68R05 (68Q25)}, MRNUMBER = {1450639}, DOI = {10.1109/SFCS.1996.548500}, URL = {http://dx.doi.org/10.1109/SFCS.1996.548500}, } @article {Lu02, AUTHOR = {Lu, Chi-Jen}, TITLE = {Improved pseudorandom generators for combinatorial rectangles}, JOURNAL = {Combinatorica}, VOLUME = {22}, YEAR = {2002}, NUMBER = {3}, PAGES = {417--433}, ISSN = {0209-9683}, MRCLASS = {60C05 (05B40 68Q25 68R05)}, MRNUMBER = {1932062 (2003h:60015)}, MRREVIEWER = {Robert P. Dobrow}, DOI = {10.1007/s004930200021}, URL = {http://dx.doi.org/10.1007/s004930200021}, } @article {Lubotzky12, AUTHOR = {Lubotzky, Alexander}, TITLE = {Expander graphs in pure and applied mathematics}, JOURNAL = {American Mathematical Society. Bulletin. New Series}, VOLUME = {49}, YEAR = {2012}, NUMBER = {1}, PAGES = {113--162}, ISSN = {0273-0979}, CODEN = {BAMOAD}, MRCLASS = {05-02 (05C99)}, MRNUMBER = {2869010}, DOI = {10.1090/S0273-0979-2011-01359-3}, URL = {http://dx.doi.org/10.1090/S0273-0979-2011-01359-3}, } @MASTERSTHESIS{Even91, author = {Guy Even}, title = {Construction of Small Probabilistic Spaces for Deterministic Simulation}, school = {The Technion}, year = {1991} } @article{EvenGoLuNiVe98, author = {Guy Even and Oded Goldreich and Michael Luby and Noam Nisan and Boban Velickovic}, title = {Efficient approximation of product distributions}, journal = {Random Struct. Algorithms}, volume = {13}, number = {1}, year = {1998}, pages = {1-16}, ee = {http://dx.doi.org/10.1002/(SICI)1098-2418(199808)13:1$<$1::AID-RSA1$>$3.0.CO;2-W}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{Saks96, author = {Michael E. Saks}, title = {Randomization and Derandomization in Space_Bounded Computation}, booktitle = {IEEE Conference on Computational Complexity}, year = {1996}, pages = {128-149}, ee = {http://www.computer.org/proceedings/ccc/7386/73860128abs.htm}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {BabaiNiSz92, AUTHOR = {Babai, L{\'a}szl{\'o} and Nisan, Noam and Szegedy, M{\'a}ri{\'o}}, TITLE = {Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs}, NOTE = {Twenty-first Symposium on the Theory of Computing (Seattle, WA, 1989)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {45}, YEAR = {1992}, NUMBER = {2}, PAGES = {204--232}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q05 (68Q15 68Q22 68Q25 68Q30)}, MRNUMBER = {1186884 (93m:68048)}, MRREVIEWER = {Norbert Blum}, DOI = {10.1016/0022-0000(92)90047-M}, URL = {http://dx.doi.org/10.1016/0022-0000(92)90047-M}, } @article {RivestShAd78, AUTHOR = {Rivest, R. L. and Shamir, A. and Adleman, L.}, TITLE = {A method for obtaining digital signatures and public-key cryptosystems}, JOURNAL = {Communications of the Association for Computing Machinery}, VOLUME = {21}, YEAR = {1978}, NUMBER = {2}, PAGES = {120--126}, ISSN = {0001-0782}, CODEN = {CACMA2}, MRCLASS = {94A05}, MRNUMBER = {700103 (83m:94003)}, MRREVIEWER = {J. L. Selfridge}, DOI = {10.1145/359340.359342}, URL = {http://dx.doi.org/10.1145/359340.359342}, } @article {DiffieHe76, AUTHOR = {Diffie, Whitfield and Hellman, Martin E.}, TITLE = {New directions in cryptography}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {IT-22}, YEAR = {1976}, NUMBER = {6}, PAGES = {644--654}, ISSN = {0018-9448}, MRCLASS = {94A10}, MRNUMBER = {0437208 (55 \#10141)}, MRREVIEWER = {J. S. Joel}, } @UNPUBLISHED{ReingoldVaWi04, author = {Omer Reingold and Salil Vadhan and Avi Wigderson}, title = {A Note on Extracting Randomness from Santha--Vazirani Sources}, note = {Unpublished manuscript}, year = {2004}, month = {September} } @article {Shamir79, AUTHOR = {Shamir, Adi}, TITLE = {How to share a secret}, JOURNAL = {Communications of the Association for Computing Machinery}, VOLUME = {22}, YEAR = {1979}, NUMBER = {11}, PAGES = {612--613}, ISSN = {0001-0782}, CODEN = {CACMA2}, MRCLASS = {94B99 (68E99)}, MRNUMBER = {549252 (80g:94070)}, DOI = {10.1145/359168.359176}, URL = {http://dx.doi.org/10.1145/359168.359176}, } @incollection {FeigenbaumKaNi90, AUTHOR = {Feigenbaum, Joan and Kannan, Sampath and Nisan, Noam}, TITLE = {Lower bounds on random-self-reducibility (extended abstract)}, BOOKTITLE = {Fifth {A}nnual {S}tructure in {C}omplexity {T}heory {C}onference ({B}arcelona, 1990)}, PAGES = {100--109}, PUBLISHER = {IEEE Comput. Soc. Press}, ADDRESS = {Los Alamitos, CA}, YEAR = {1990}, MRCLASS = {68Q25}, MRNUMBER = {1097661}, DOI = {10.1109/SCT.1990.113959}, URL = {http://dx.doi.org/10.1109/SCT.1990.113959}, } @article {AbadiFeKi89, AUTHOR = {Abadi, Mart{\'{\i}}n and Feigenbaum, Joan and Kilian, Joe}, TITLE = {On hiding information from an oracle}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {39}, YEAR = {1989}, NUMBER = {1}, PAGES = {21--50}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q05 (03D15 68Q15)}, MRNUMBER = {1013719 (90m:68033)}, MRREVIEWER = {Uwe Sch{\"o}ning}, DOI = {10.1016/0022-0000(89)90018-4}, URL = {http://dx.doi.org/10.1016/0022-0000(89)90018-4}, } @article {LinialNi90, AUTHOR = {Linial, Nathan and Nisan, Noam}, TITLE = {Approximate inclusion-exclusion}, JOURNAL = {Combinatorica}, VOLUME = {10}, YEAR = {1990}, NUMBER = {4}, PAGES = {349--365}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05D05 (33C45)}, MRNUMBER = {1099249 (92d:05167)}, MRREVIEWER = {Christian Radoux}, DOI = {10.1007/BF02128670}, URL = {http://dx.doi.org/10.1007/BF02128670}, } @article {GoldreichKrLu93, AUTHOR = {Goldreich, Oded and Krawczyk, Hugo and Luby, Michael}, TITLE = {On the existence of pseudorandom generators}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {22}, YEAR = {1993}, NUMBER = {6}, PAGES = {1163--1175}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {11K45 (11T71 65C10)}, MRNUMBER = {1247182 (95f:11054)}, DOI = {10.1137/0222069}, URL = {http://dx.doi.org/10.1137/0222069}, } @INCOLLECTION{GoldreichVaWi11, author = {Oded Goldreich and Salil Vadhan and Avi Wigderson}, title = {Simplified Derandomization of BPP Using a Hitting Set Generator}, booktitle = {Studies in Complexity and Cryptography. Miscellanea on the Interplay of Randomness and Computation}, publisher = {Springer}, year = {2011}, OPTeditor = {}, volume = {6650}, OPTnumber = {}, series = {Lecture Notes in Computer Science}, OPTtype = {}, OPTchapter = {}, pages = {59--67}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, } @INCOLLECTION{Goldreich11, author = {Oded Goldreich}, title = {In a World of {P}={BPP}}, booktitle = {Studies in Complexity and Cryptography. Miscellanea on the Interplay of Randomness and Computation}, publisher = {Springer}, year = {2011}, OPTeditor = {}, volume = {6650}, OPTnumber = {}, series = {Lecture Notes in Computer Science}, OPTtype = {}, OPTchapter = {}, pages = {191--232}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, } @article {AndreevClRo98, AUTHOR = {Andreev, Alexander E. and Clementi, Andrea E. F. and Rolim, Jos{\'e} D. P.}, TITLE = {A new general derandomization method}, JOURNAL = {Journal of the ACM}, VOLUME = {45}, YEAR = {1998}, NUMBER = {1}, PAGES = {179--213}, ISSN = {0004-5411}, MRCLASS = {68Q25 (68W25)}, MRNUMBER = {1614340 (2000c:68064)}, DOI = {10.1145/273865.273933}, URL = {http://dx.doi.org/10.1145/273865.273933}, } @incollection {ImpagliazzoRu88, AUTHOR = {Impagliazzo, Russell and Rudich, Steven}, TITLE = {Limits on the provable consequences of one-way permutations}, BOOKTITLE = {Advances in cryptology---{CRYPTO} '88 ({S}anta {B}arbara, {CA}, 1988)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {403}, PAGES = {8--26}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1990}, MRCLASS = {94A60 (03D80 68P25 68Q05)}, MRNUMBER = {1046378 (91i:94028)}, MRREVIEWER = {Joan Boyar}, DOI = {10.1007/0-387-34799-2_2}, URL = {http://dx.doi.org/10.1007/0-387-34799-2_2}, } @ARTICLE{TrevisanVa07, AUTHOR = "Luca Trevisan and Salil Vadhan", TITLE = "Pseudorandomness and Average-Case Complexity via Uniform Reductions", JOURNAL = "Computational Complexity", YEAR = "2007", volume = "16", number = "4", pages = "331--364", month = "December", OPTnote = "Preliminary version in {\em CCC `02}", file = F } @article {ChorGoKuSu98, AUTHOR = {Chor, Benny and Goldreich, Oded and Kushilevitz, Eyal and Sudan, Madhu}, TITLE = {Private information retrieval}, JOURNAL = {Journal of the ACM}, VOLUME = {45}, YEAR = {1998}, NUMBER = {6}, PAGES = {965--982}, ISSN = {0004-5411}, MRCLASS = {68P15 (68P25 94A60)}, MRNUMBER = {1678848 (2000b:68055)}, DOI = {10.1145/293347.293350}, URL = {http://dx.doi.org/10.1145/293347.293350}, } @incollection {Ambainis97, AUTHOR = {Ambainis, Andris}, TITLE = {Upper bound on the communication complexity of private information retrieval}, BOOKTITLE = {Automata, languages and programming ({B}ologna, 1997)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {1256}, PAGES = {401--407}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1997}, MRCLASS = {68P15}, MRNUMBER = {1616202}, } @inproceedings{LubyVeWi93, author = {Michael Luby and Boban Veli{\v{c}}kovi{\'c} and Avi Wigderson}, title = {Deterministic Approximate Counting of Depth-2 Circuits}, booktitle = {ISTCS}, year = {1993}, pages = {18-24}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {LubyVe96, AUTHOR = {Michael Luby and Boban Veli{\v{c}}kovi{\'c}}, TITLE = {On deterministic approximation of {DNF}}, JOURNAL = {Algorithmica}, VOLUME = {16}, YEAR = {1996}, NUMBER = {4-5}, PAGES = {415--433}, ISSN = {0178-4617}, CODEN = {ALGOEJ}, MRCLASS = {68Q25 (68Q15)}, MRNUMBER = {1407582 (97d:68089)}, DOI = {10.1007/s004539900054}, URL = {http://dx.doi.org/10.1007/s004539900054}, } @BOOK{Hastad87, author = {Johan H{\aa}stad}, title = {Computational Limitations of Small-Depth Circuits}, publisher = {MIT Press}, year = {1987} } @INCOLLECTION{AjtaiWi89, author = {Mikl{\'o}s Ajtai and Avi Wigderson}, title = {Deterministic Simulation of Probabilistic Constant Depth Circuits}, booktitle = {Randomness and Computation}, publisher = {JAI Press Inc.}, year = {1989}, editor = {Franco P. Preparata and Silvio Micali}, volume = {5}, series = {Advances in Computing Research}, pages = {199--223} } @MISC{Reingold06, author = {Omer Reingold}, title = {On black-box separations in cryptography}, howpublished = {Tutorial at the Third Theory of Cryptography Conference (TCC `06)}, year = {2006}, month = {March}, note = {Slides available from http://research.microsoft.com/en-us/people/omreing/} } @inproceedings{DBLP:conf/stoc/ImpagliazzoR89, author = {Russell Impagliazzo and Steven Rudich}, title = {Limits on the Provable Consequences of One-Way Permutations}, booktitle = {STOC}, year = {1989}, pages = {44-61}, ee = {http://doi.acm.org/10.1145/73007.73012}, crossref = {DBLP:conf/stoc/STOC21}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC21, editor = {David S. Johnson}, title = {Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1989}, isbn = {0-89791-307-8}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{GemmellLiRuSuWi91, author = {Peter Gemmell and Richard J. Lipton and Ronitt Rubinfeld and Madhu Sudan and Avi Wigderson}, title = {Self-Testing/Correcting for Polynomials and for Approximate Functions}, booktitle = {STOC}, year = {1991}, pages = {32-42}, ee = {http://doi.acm.org/10.1145/103418.103429}, crossref = {DBLP:conf/stoc/STOC23}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC23, editor = {Cris Koutsougeras and Jeffrey Scott Vitter}, title = {Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1991}, isbn = {0-89791-397-3}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {GemmellSu92, AUTHOR = {Gemmell, Peter and Sudan, Madhu}, TITLE = {Highly resilient correctors for polynomials}, JOURNAL = {Information Processing Letters}, VOLUME = {43}, YEAR = {1992}, NUMBER = {4}, PAGES = {169--174}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {68Q40}, MRNUMBER = {1187182 (93h:68066)}, DOI = {10.1016/0020-0190(92)90195-2}, URL = {http://dx.doi.org/10.1016/0020-0190(92)90195-2}, } @article {Levin87, AUTHOR = {Levin, L. A.}, TITLE = {One way functions and pseudorandom generators}, JOURNAL = {Combinatorica}, VOLUME = {7}, YEAR = {1987}, NUMBER = {4}, PAGES = {357--363}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68Q25 (03D15 65C10)}, MRNUMBER = {931193 (89c:68048)}, MRREVIEWER = {Cristian Calude}, DOI = {10.1007/BF02579323}, URL = {http://dx.doi.org/10.1007/BF02579323}, } @BOOK{Yekhanin12, AUTHOR = {Sergey Yekhanin}, OPTeditor = {}, TITLE = {Locally Decodable Codes}, PUBLISHER = {Now Publishers}, YEAR = {2012}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, note = {To appear}, OPTabstract = {}, OPTisbn = {}, OPTprice = {}, OPTkeywords = {}, OPTsource = {}, } @article {RazborovRu97, AUTHOR = {Razborov, Alexander A. and Rudich, Steven}, TITLE = {Natural proofs}, NOTE = {26th Annual ACM Symposium on the Theory of Computing (STOC '94) (Montreal, PQ, 1994)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {55}, YEAR = {1997}, NUMBER = {1, part 1}, PAGES = {24--35}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (68Q10 68Q25 94C10)}, MRNUMBER = {1473047 (98m:68094)}, MRREVIEWER = {Juraj Hromkovi{\v{c}}}, DOI = {10.1006/jcss.1997.1494}, URL = {http://dx.doi.org/10.1006/jcss.1997.1494}, } @article {FriezeHaKaLaSh88, AUTHOR = {Frieze, Alan M. and H{\aa}stad, Johan and Kannan, Ravi and Lagarias, Jeffrey C. and Shamir, Adi}, TITLE = {Reconstructing truncated integer variables satisfying linear congruences}, NOTE = {Special issue on cryptography}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {17}, YEAR = {1988}, NUMBER = {2}, PAGES = {262--280}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {11Y16 (11T71 94A60)}, MRNUMBER = {935340 (89d:11115)}, MRREVIEWER = {Harald Niederreiter}, DOI = {10.1137/0217016}, URL = {http://dx.doi.org/10.1137/0217016}, } @inproceedings{Stern87, author = {Jacques Stern}, title = {Secret Linear Congruential Generators Are Not Cryptographically Secure}, booktitle = {FOCS}, year = {1987}, pages = {421-426}, ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1987.51}, crossref = {DBLP:conf/focs/FOCS28}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/FOCS28, title = {28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {1987}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{BellareGoMi97, author = {Mihir Bellare and Shafi Goldwasser and Daniele Micciancio}, title = {``Pseudo-Random'' Number Generation Within Cryptographic Algorithms: The DDS Case}, booktitle = {CRYPTO}, year = {1997}, pages = {277-291}, ee = {http://dx.doi.org/10.1007/BFb0052242}, crossref = {DBLP:conf/crypto/1997}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/crypto/1997, editor = {Burton S. Kaliski Jr.}, title = {Advances in Cryptology - CRYPTO '97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings}, booktitle = {CRYPTO}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {1294}, year = {1997}, isbn = {3-540-63384-7}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Krawczyk92, AUTHOR = {Krawczyk, Hugo}, TITLE = {How to predict congruential generators}, JOURNAL = {Journal of Algorithms}, VOLUME = {13}, YEAR = {1992}, NUMBER = {4}, PAGES = {527--545}, ISSN = {0196-6774}, CODEN = {JOALDV}, MRCLASS = {65C10 (94A60)}, MRNUMBER = {1187200 (93g:65013)}, DOI = {10.1016/0196-6774(92)90054-G}, URL = {http://dx.doi.org/10.1016/0196-6774(92)90054-G}, } @article {Boyar89, AUTHOR = {Boyar, Joan}, TITLE = {Inferring sequences produced by pseudo-random number generators}, JOURNAL = {Journal of the Association for Computing Machinery}, VOLUME = {36}, YEAR = {1989}, NUMBER = {1}, PAGES = {129--141}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68P25 (68Q25)}, MRNUMBER = {1072416 (91g:68035)}, DOI = {10.1145/58562.59305}, URL = {http://dx.doi.org/10.1145/58562.59305}, } @inproceedings{Shaltiel11-affine, author = {Ronen Shaltiel}, title = {Dispersers for Affine Sources with Sub-polynomial Entropy}, booktitle = {FOCS}, year = {2011}, pages = {247-256}, ee = {http://dx.doi.org/10.1109/FOCS.2011.37}, crossref = {DBLP:conf/focs/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2011, editor = {Rafail Ostrovsky}, title = {IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011}, booktitle = {FOCS}, publisher = {IEEE}, year = {2011}, isbn = {978-1-4577-1843-4}, ee = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {Shaltiel11-extractorsurvey, AUTHOR = {Shaltiel, Ronen}, TITLE = {An introduction to randomness extractors}, BOOKTITLE = {Automata, languages and programming. {P}art {II}}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6756}, PAGES = {21--41}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {68W20 (68Q87)}, MRNUMBER = {2852413}, DOI = {10.1007/978-3-642-22012-8_2}, URL = {http://dx.doi.org/10.1007/978-3-642-22012-8_2}, } @MISC{NIST10, AUTHOR = {Andrew Rukhin and Juan Soto and James Nechvatal and Miles Smid and Elaine Barker and Stefan Leigh and Mark Levenson and Mark Vangel and David Banks and Alan Heckert and James Dray and San Vo}, TITLE = {A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications}, howpublished = {National Institute of Standards and Technology, U.S. Department of Commerce, Special Publication 800-22, Revision 1a}, year = {2010}, month = {April} } @MISC{NIST12, AUTHOR = {Elaine Barker and John Kelsey}, TITLE = {Recommendation for Random Number Generation Using Deterministic Random Bit Generators}, howpublished = {National Institute of Standards and Technology, U.S. Department of Commerce, Special Publication 800-90A}, year = {2012}, month = {January} } @book {Knuth98, AUTHOR = {Knuth, Donald E.}, TITLE = {The art of computer programming. {V}olume 2: Seminumerical Algorithms}, EDITION = {Third}, YEAR = {1998}, PUBLISHER = {Addison--Wesley} } @incollection {Efremenko09, AUTHOR = {Efremenko, Klim}, TITLE = {3-query locally decodable codes of subexponential length}, BOOKTITLE = {S{TOC}'09---{P}roceedings of the 2009 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing}, PAGES = {39--44}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2009}, MRCLASS = {94B35 (68P30 94A60 94B60)}, MRNUMBER = {2780048}, MRREVIEWER = {Vitaly Skachek}, } @incollection {Yekhanin11, AUTHOR = {Yekhanin, Sergey}, TITLE = {Locally decodable codes: a brief survey}, BOOKTITLE = {Coding and cryptology}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6639}, PAGES = {273--282}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {94B05 (94B99)}, MRNUMBER = {2834707}, DOI = {10.1007/978-3-642-20901-7_18}, URL = {http://dx.doi.org/10.1007/978-3-642-20901-7_18}, } @article {DvirGoYe11, AUTHOR = {Dvir, Zeev and Gopalan, Parikshit and Yekhanin, Sergey}, TITLE = {Matching vector codes}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {40}, YEAR = {2011}, NUMBER = {4}, PAGES = {1154--1178}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {94A24 (68P30)}, MRNUMBER = {2861716}, DOI = {10.1137/100804322}, URL = {http://dx.doi.org/10.1137/100804322}, } @article {KedlayaYe08, AUTHOR = {Kedlaya, Kiran S. and Yekhanin, Sergey}, TITLE = {Locally decodable codes from nice subsets of finite fields and prime factors of {M}ersenne numbers}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {38}, YEAR = {2008/09}, NUMBER = {5}, PAGES = {1952--1969}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {94B60 (11L05 94B40)}, MRNUMBER = {2476281 (2010b:94100)}, MRREVIEWER = {Robin Chapman}, DOI = {10.1137/070696519}, URL = {http://dx.doi.org/10.1137/070696519}, } @article {Yekhanin08, AUTHOR = {Yekhanin, Sergey}, TITLE = {Towards 3-query locally decodable codes of subexponential length}, JOURNAL = {Journal of the ACM}, VOLUME = {55}, YEAR = {2008}, NUMBER = {1}, PAGES = {Art. 1, 16}, ISSN = {0004-5411}, MRCLASS = {94B60 (94B35 94B65)}, MRNUMBER = {2388223 (2010a:94125)}, MRREVIEWER = {Ana Maria Salagean}, DOI = {10.1145/1326554.1326555}, URL = {http://dx.doi.org/10.1145/1326554.1326555}, } @incollection {BeaverFe90, AUTHOR = {Beaver, Donald and Feigenbaum, Joan}, TITLE = {Hiding instances in multioracle queries (extended abstract)}, BOOKTITLE = {S{TACS} 90 ({R}ouen, 1990)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {415}, PAGES = {37--48}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1990}, MRCLASS = {68Q15 (03D10)}, MRNUMBER = {1063302}, } @article{BlumKa95, author = {Manuel Blum and Sampath Kannan}, title = {Designing Programs that Check Their Work}, journal = {Journal of the ACM}, volume = {42}, number = {1}, year = {1995}, pages = {269-291}, ee = {http://doi.acm.org/10.1145/200836.200880}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {Lipton89, AUTHOR = {Lipton, Richard J.}, TITLE = {New directions in testing}, BOOKTITLE = {Distributed computing and cryptography ({P}rinceton, {NJ}, 1989)}, SERIES = {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.}, VOLUME = {2}, PAGES = {191--202}, PUBLISHER = {Amer. Math. Soc.}, ADDRESS = {Providence, RI}, YEAR = {1991}, MRCLASS = {68Q60}, MRNUMBER = {1105541 (92c:68127)}, } @article {GoldreichSu99, AUTHOR = {Goldreich, Oded and Sudan, Madhu}, TITLE = {Computational indistinguishability: a sample hierarchy}, NOTE = {13th Annual IEEE Conference on Computation Complexity (Buffalo, NY, 1998)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {59}, YEAR = {1999}, NUMBER = {2}, PAGES = {253--269}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q99}, MRNUMBER = {1723485 (2001a:68072)}, MRREVIEWER = {Jay Belanger}, DOI = {10.1006/jcss.1999.1652}, URL = {http://dx.doi.org/10.1006/jcss.1999.1652}, } @article {Braverman10, AUTHOR = {Braverman, Mark}, TITLE = {Polylogarithmic independence fools {${\rm AC}^0$} circuits}, JOURNAL = {Journal of the ACM}, VOLUME = {57}, YEAR = {2010}, NUMBER = {5}, PAGES = {Art. 28, 10}, ISSN = {0004-5411}, MRCLASS = {68Q15 (60E99)}, MRNUMBER = {2683586 (2011k:68038)}, DOI = {10.1145/1754399.1754401}, URL = {http://dx.doi.org/10.1145/1754399.1754401}, } @article {GoldreichMe98, AUTHOR = {Goldreich, Oded and Meyer, Bernd}, TITLE = {Computational indistinguishability: algorithms vs.\ circuits}, JOURNAL = {Theoretical Computer Science}, VOLUME = {191}, YEAR = {1998}, NUMBER = {1-2}, PAGES = {215--218}, ISSN = {0304-3975}, CODEN = {TCSDI}, MRCLASS = {68Q15 (68Q05)}, MRNUMBER = {1490574 (98h:68086)}, DOI = {10.1016/S0304-3975(97)00162-X}, URL = {http://dx.doi.org/10.1016/S0304-3975(97)00162-X}, } @incollection {Shamir81, AUTHOR = {Shamir, Adi}, TITLE = {On the generation of cryptographically strong pseudorandom sequences}, BOOKTITLE = {Automata, languages and programming ({A}kko, 1981)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {115}, PAGES = {544--550}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1981}, MRCLASS = {65C10 (10K10 68C05)}, MRNUMBER = {635160 (82m:65007)}, } @article {BlumMi84, AUTHOR = {Blum, Manuel and Micali, Silvio}, TITLE = {How to generate cryptographically strong sequences of pseudorandom bits}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {13}, YEAR = {1984}, NUMBER = {4}, PAGES = {850--864}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68P25 (65C10 68Q20)}, MRNUMBER = {764183 (86a:68021)}, DOI = {10.1137/0213053}, URL = {http://dx.doi.org/10.1137/0213053}, } @article {PippengerFi79, AUTHOR = {Pippenger, Nicholas and Fischer, Michael J.}, TITLE = {Relations among complexity measures}, JOURNAL = {Journal of the Association for Computing Machinery}, VOLUME = {26}, YEAR = {1979}, NUMBER = {2}, PAGES = {361--381}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68C25 (03D15 68J05)}, MRNUMBER = {528038 (80f:68052)}, MRREVIEWER = {Eugene Levner}, DOI = {10.1145/322123.322138}, URL = {http://dx.doi.org/10.1145/322123.322138}, } @article {AllenderBuKoMeRo06, AUTHOR = {Allender, Eric and Buhrman, Harry and Kouck{\'y}, Michal and van Melkebeek, Dieter and Ronneburger, Detlef}, TITLE = {Power from random strings}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {35}, YEAR = {2006}, NUMBER = {6}, PAGES = {1467--1493 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q30 (03D15 68Q10 68Q15 68Q17)}, MRNUMBER = {2217153 (2006m:68056)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1137/050628994}, URL = {http://dx.doi.org/10.1137/050628994}, } @book {LiVi08, AUTHOR = {Li, Ming and Vit{\'a}nyi, Paul}, TITLE = {An introduction to {K}olmogorov complexity and its applications}, SERIES = {Texts in Computer Science}, EDITION = {Third}, PUBLISHER = {Springer}, ADDRESS = {New York}, YEAR = {2008}, PAGES = {xxiv+790}, ISBN = {978-0-387-33998-6}, MRCLASS = {68Q30 (62B10 62P99 68-02 94A15)}, MRNUMBER = {2494387 (2010c:68058)}, DOI = {10.1007/978-0-387-49820-1}, URL = {http://dx.doi.org/10.1007/978-0-387-49820-1}, } @UNPUBLISHED{Guruswami10, AUTHOR = {Venkatesan Guruswami}, TITLE = {Linear-algebraic list decoding of folded Reed-Solomon codes}, NOTE = {Unpublished manuscript}, year = {2010}, month = {December} } @inproceedings {KaplanNaRe05, AUTHOR = {Eyal Kaplan and Moni Naor and Omer Reingold}, TITLE = {Derandomized Constructions of $k$-Wise (Almost) Independent Permutations}, BOOKTITLE = "Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM `05)", YEAR = "2005", number = "3624", series = "Lecture Notes in Computer Science", pages = "354 -- 365", address = "Berkeley, CA", month = "August", publisher = "Springer", } @inproceedings{MekaZu09, author = {Raghu Meka and David Zuckerman}, title = {Small-Bias Spaces for Group Products}, booktitle = {APPROX-RANDOM}, year = {2009}, pages = {658-672}, ee = {http://dx.doi.org/10.1007/978-3-642-03685-9_49}, crossref = {DBLP:conf/approx/2009}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/approx/2009, editor = {Irit Dinur and Klaus Jansen and Joseph Naor and Jos{\'e} D. P. Rolim}, title = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings}, booktitle = {APPROX-RANDOM}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {5687}, year = {2009}, isbn = {978-3-642-03684-2}, ee = {http://dx.doi.org/10.1007/978-3-642-03685-9}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Yehudayoff11, AUTHOR = {Yehudayoff, Amir}, TITLE = {Affine extractors over prime fields}, JOURNAL = {Combinatorica}, VOLUME = {31}, YEAR = {2011}, NUMBER = {2}, PAGES = {245--256}, ISSN = {0209-9683}, MRCLASS = {11T23 (11L07)}, MRNUMBER = {2848253 (2012j:11233)}, MRREVIEWER = {Alessandro Conflitti}, DOI = {10.1007/s00493-011-2604-9}, URL = {http://dx.doi.org/10.1007/s00493-011-2604-9}, } @article {Gowers01, AUTHOR = {Gowers, W. T.}, TITLE = {A new proof of {S}zemer\'edi's theorem}, JOURNAL = {Geometric and Functional Analysis}, VOLUME = {11}, YEAR = {2001}, NUMBER = {3}, PAGES = {465--588}, ISSN = {1016-443X}, CODEN = {GFANFB}, MRCLASS = {11B25 (11K38 11K45)}, MRNUMBER = {1844079 (2002k:11014)}, MRREVIEWER = {Hillel Furstenberg}, DOI = {10.1007/s00039-001-0332-9}, URL = {http://dx.doi.org/10.1007/s00039-001-0332-9}, } @article {GuruswamiHaKo11, AUTHOR = {Guruswami, Venkatesan and H{\aa}stad, Johan and Kopparty, Swastik}, TITLE = {On the list-decodability of random linear codes}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {57}, YEAR = {2011}, NUMBER = {2}, PAGES = {718--725}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B35 (94B05)}, MRNUMBER = {2807801 (2012f:94171)}, MRREVIEWER = {Bram van Asch}, DOI = {10.1109/TIT.2010.2095170}, URL = {http://dx.doi.org/10.1109/TIT.2010.2095170}, } @article {Gowers98, AUTHOR = {Gowers, W. T.}, TITLE = {A new proof of {S}zemer\'edi's theorem for arithmetic progressions of length four}, JOURNAL = {Geometric and Functional Analysis}, VOLUME = {8}, YEAR = {1998}, NUMBER = {3}, PAGES = {529--551}, ISSN = {1016-443X}, CODEN = {GFANFB}, MRCLASS = {11B25 (11N13)}, MRNUMBER = {1631259 (2000d:11019)}, MRREVIEWER = {D. R. Heath-Brown}, DOI = {10.1007/s000390050065}, URL = {http://dx.doi.org/10.1007/s000390050065}, } @article {Lovett09, AUTHOR = {Lovett, Shachar}, TITLE = {Unconditional pseudorandom generators for low-degree polynomials}, JOURNAL = {Theory of Computing. An Open Access Journal}, VOLUME = {5}, YEAR = {2009}, PAGES = {69--82}, ISSN = {1557-2862}, MRCLASS = {68Q10 (12Y05 60-08 68Q17)}, MRNUMBER = {2521350 (2011a:68031)}, } @article {BogdanovVi10, AUTHOR = {Bogdanov, Andrej and Viola, Emanuele}, TITLE = {Pseudorandom bits for polynomials}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {39}, YEAR = {2010}, NUMBER = {6}, PAGES = {2464--2486}, ISSN = {0097-5397}, MRCLASS = {68Q87 (68Q15 68Q17 68W20)}, MRNUMBER = {2644354}, DOI = {10.1137/070712109}, URL = {http://dx.doi.org/10.1137/070712109}, } @article {Viola09, AUTHOR = {Viola, Emanuele}, TITLE = {The sum of {$d$} small-bias generators fools polynomials of degree {$d$}}, JOURNAL = {Computational Complexity}, VOLUME = {18}, YEAR = {2009}, NUMBER = {2}, PAGES = {209--217}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q99 (11K45 68W20)}, MRNUMBER = {2520092}, DOI = {10.1007/s00037-009-0273-5}, URL = {http://dx.doi.org/10.1007/s00037-009-0273-5}, } @article {SrinivasanZu99, AUTHOR = {Srinivasan, Aravind and Zuckerman, David}, TITLE = {Computing with very weak random sources}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {28}, YEAR = {1999}, NUMBER = {4}, PAGES = {1433--1459 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68W20 (65C10 68Q15 94A17)}, MRNUMBER = {1681073 (2001d:68234)}, DOI = {10.1137/S009753979630091X}, URL = {http://dx.doi.org/10.1137/S009753979630091X}, } @article {SaksSrZh98, AUTHOR = {Saks, Michael and Srinivasan, Aravind and Zhou, Shiyu}, TITLE = {Explicit {OR}-dispersers with polylogarithmic degree}, JOURNAL = {Journal of the ACM}, VOLUME = {45}, YEAR = {1998}, NUMBER = {1}, PAGES = {123--154}, ISSN = {0004-5411}, MRCLASS = {68Q15 (68Q25 68R05 68R10)}, MRNUMBER = {MR1614332 (99c:68099)}, MRREVIEWER = {Ralf Klasing}, DOI = {10.1145/273865.273915}, URL = {http://dx.doi.org/10.1145/273865.273915}, } @article {BennettBrRo88, AUTHOR = {Bennett, Charles H. and Brassard, Gilles and Robert, Jean-Marc}, TITLE = {Privacy amplification by public discussion}, NOTE = {Special issue on cryptography}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {17}, YEAR = {1988}, NUMBER = {2}, PAGES = {210--229}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {94A40 (94A13 94A60)}, MRNUMBER = {MR935338 (89c:94028)}, MRREVIEWER = {Thomas Beth}, DOI = {10.1137/0217014}, URL = {http://dx.doi.org/10.1137/0217014}, } @ARTICLE{Elias72, AUTHOR = {Peter Elias}, TITLE = {The Efficient Construction of an Unbiased Random Sequence}, JOURNAL = {The Annals of Mathematical Statistics}, YEAR = {1972}, volume = {43}, number = {3}, pages = {865--870}, month = {June}, url = {http://www.jstor.org/stable/2240383} } @INCOLLECTION{vonNeumann63, AUTHOR = {{von N}eumann, John}, TITLE = {Various techniques used in conjunction with random digits}, BOOKTITLE = {Collected works. {V}ol. {V}: {D}esign of computers, theory of automata and numerical analysis}, PUBLISHER = {The Macmillan Co.}, ADDRESS = {New York}, YEAR = {1963} } @ARTICLE{vonNeumann51, AUTHOR = {John von Neumann}, TITLE = {Various techniques used in conjunction with random digits}, JOURNAL = {National Bureau of Standards Applied Math Series}, YEAR = {1951}, volume = {12}, OPTnumber = {}, pages = {36--38} } @article {Peres92, AUTHOR = {Peres, Yuval}, TITLE = {Iterating von {N}eumann's procedure for extracting random bits}, JOURNAL = {The Annals of Statistics}, VOLUME = {20}, YEAR = {1992}, NUMBER = {1}, PAGES = {590--597}, ISSN = {0090-5364}, CODEN = {ASTSC7}, MRCLASS = {94A29}, MRNUMBER = {MR1150365 (93b:94015)}, MRREVIEWER = {L. L. Campbell}, DOI = {10.1214/aos/1176348543}, URL = {http://dx.doi.org/10.1214/aos/1176348543}, } @MISC{Sudan01, author = {Madhu Sudan}, title = {Algorithmic Introduction to Coding Theory}, howpublished = {Lecture notes}, year = {2001}, OPTmonth = {}, note = {\url{http://people.csail.mit.edu/madhu/FT01/}}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @ARTICLE{Gilbert52, AUTHOR = {E.N. Gilbert}, TITLE = {A comparison of signalling alphabets}, JOURNAL = {Bell Systems Technical Journal}, YEAR = {1952}, volume = {31}, pages = {504--522} } @ARTICLE{Varshamov57, AUTHOR = {R.R. Varshamov}, TITLE = {Estimate of the number of signals in error correcting codes}, JOURNAL = {Doklady Akad. Nauk SSSR}, YEAR = {1957}, volume = {117}, pages = {739--741} } @article {Slepian56, AUTHOR = {Slepian, David}, TITLE = {A class of binary signaling alphabets}, JOURNAL = {The Bell System Technical Journal}, VOLUME = {35}, YEAR = {1956}, PAGES = {203--234}, ISSN = {0005-8580}, MRCLASS = {60.0X}, MRNUMBER = {MR0077820 (17,1100c)}, MRREVIEWER = {S. Gorn}, } @book {HandbookCoding98, TITLE = {Handbook of coding theory. {V}ol. {I}, {II}}, EDITOR = {Pless, V. S. and Huffman, W. C. and Brualdi, R. A.}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {1998}, PAGES = {Vol. I: xvi+1138+I-58 pp.; Vol. II: pp. i--xvi, 1139--2169 and I-1--I-58}, ISBN = {0-444-50088-X}, MRCLASS = {94-02 (94Bxx)}, MRNUMBER = {MR1667936 (2000h:94001)}, } @article {SanthaVa86, AUTHOR = {S{\'a}ntha, Mikl{\'o}s and Vazirani, Umesh V.}, TITLE = {Generating quasirandom sequences from semirandom sources}, NOTE = {Twenty-fifth annual symposium on foundations of computer science (Singer Island, Fla., 1984)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {33}, YEAR = {1986}, NUMBER = {1}, PAGES = {75--87}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q99 (65C10 68Q25 68U20)}, MRNUMBER = {MR864080 (88b:68154)}, DOI = {10.1016/0022-0000(86)90044-9}, URL = {http://dx.doi.org/10.1016/0022-0000(86)90044-9}, } @article {GuruswamiHaSuZu02, AUTHOR = {Guruswami, Venkatesan and H{\aa}stad, Johan and Sudan, Madhu and Zuckerman, David}, TITLE = {Combinatorial bounds for list decoding}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {48}, YEAR = {2002}, NUMBER = {5}, PAGES = {1021--1034}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B35 (94B25)}, MRNUMBER = {MR1907395 (2003f:94095)}, DOI = {10.1109/18.995539}, URL = {http://dx.doi.org/10.1109/18.995539}, } @article {ZyablovPi81, AUTHOR = {Zyablov, V. V. and Pinsker, M. S.}, TITLE = {List cascade decoding (in Russian)}, JOURNAL = {Problems of Information Transmission}, VOLUME = {17}, NUMBER = {4}, PAGES = {29--33}, YEAR = {1981}, MRCLASS = {94B60}, MRNUMBER = {MR673744 (83j:94026)}, } @article {Gilbert71, AUTHOR = {Gilbert, Edgar N.}, TITLE = {Codes based on inaccurate source probabilities}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {IT-17}, YEAR = {1971}, PAGES = {304--314}, ISSN = {0018-9448}, MRCLASS = {94A10}, MRNUMBER = {MR0312983 (47 \#1538)}, MRREVIEWER = {Toby Berger}, } @article {Varshamov73, AUTHOR = {Varshamov, R. R.}, TITLE = {A class of codes for asymmetric channels and a problem from the additive theory of numbers}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {IT-19}, YEAR = {1973}, NUMBER = {1}, PAGES = {92--95}, ISSN = {0018-9448}, MRCLASS = {94A10}, MRNUMBER = {MR0406690 (53 \#10476)}, MRREVIEWER = {J. J. Stiffler}, } @article {Varshamov70, AUTHOR = {Varshamov, R. R.}, TITLE = {A general method of constructing asymmetric coding systems, related to the solution of a combinatorial problem proposed by {D}ixon}, JOURNAL = {Dokl. Akad. Nauk SSSR}, FJOURNAL = {Dokl. Akad. Nauk SSSR}, VOLUME = {194}, YEAR = {1970}, NUMBER = {}, PAGES = {284--287}, MRCLASS = {94A10}, MRNUMBER = {MR0316167 (47 \#4715)}, MRREVIEWER = {G. Solomon}, } @article {ChungGrLe01, AUTHOR = {Chung, Fan and Graham, Ronald and Leighton, Tom}, TITLE = {Guessing secrets}, JOURNAL = {Electronic Journal of Combinatorics}, VOLUME = {8}, YEAR = {2001}, NUMBER = {1}, PAGES = {Research Paper 13, 25 pp. (electronic)}, ISSN = {1077-8926}, MRCLASS = {05C65 (68R05 91A40)}, MRNUMBER = {MR1814520 (2002a:05186)}, MRREVIEWER = {Garth T. Isaak}, URL = {http://www.combinatorics.org/Volume_8/Abstracts/v8i1r13.html}, } @ARTICLE{Guruswami06-EATCS, AUTHOR = {Venkatesan Guruswami}, TITLE = {Iterative Decoding of Low-Density Parity-Check Codes}, JOURNAL = {Bulletin of the EATCS}, YEAR = {2006}, volume = {90}, pages = {53--88}, month = {October} } @article {Tanner81, AUTHOR = {Tanner, R. Michael}, TITLE = {A recursive approach to low complexity codes}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {27}, YEAR = {1981}, NUMBER = {5}, PAGES = {533--547}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B25 (05C99 94B20)}, MRNUMBER = {MR650686 (83i:94017)}, MRREVIEWER = {E. F. Assmus, Jr.}, DOI = {10.1109/TIT.1981.1056404}, URL = {http://dx.doi.org/10.1109/TIT.1981.1056404}, } @inproceedings{GuruswamiSu00, author = {Venkatesan Guruswami and Madhu Sudan}, title = {List decoding algorithms for certain concatenated codes}, booktitle = {STOC}, year = {2000}, pages = {181-190}, ee = {http://doi.acm.org/10.1145/335305.335327}, bibsource = {DBLP, http://dblp.uni-trier.de} } @BOOK{Gallager63, AUTHOR = {R. G. Gallager}, TITLE = {Low-Density Parity-Check Codes}, PUBLISHER = {MIT Press}, YEAR = {1963} } @BOOK{Forney66, AUTHOR = {G. David Forney}, OPTeditor = {}, TITLE = {Concatenated Codes}, PUBLISHER = {MIT Press}, YEAR = {1966} } @article {AlonGuKaSu07, AUTHOR = {Alon, Noga and Guruswami, Venkatesan and Kaufman, Tali and Sudan, Madhu}, TITLE = {Guessing secrets efficiently via list decoding}, JOURNAL = {ACM Transactions on Algorithms}, VOLUME = {3}, YEAR = {2007}, NUMBER = {4}, PAGES = {Art. 42, 16}, ISSN = {1549-6325}, MRCLASS = {94B35 (68R05 68W40 91A46 94A15)}, MRNUMBER = {MR2364966 (2008j:94069)}, DOI = {10.1145/1290672.1290679}, URL = {http://dx.doi.org/10.1145/1290672.1290679}, } @article {GuruswamiSu99, AUTHOR = {Guruswami, Venkatesan and Sudan, Madhu}, TITLE = {Improved decoding of {R}eed-{S}olomon and algebraic-geometry codes}, JOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory}, VOLUME = {45}, YEAR = {1999}, NUMBER = {6}, PAGES = {1757--1767}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B05 (94B27 94B35)}, MRNUMBER = {MR1720630 (2000j:94033)}, DOI = {10.1109/18.782097}, URL = {http://dx.doi.org/10.1109/18.782097}, } @article {Massey69, AUTHOR = {Massey, James L.}, TITLE = {Shift-register synthesis and {${\rm BCH}$} decoding}, JOURNAL = {IEEE Trans. Information Theory}, FJOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory}, VOLUME = {IT-15}, YEAR = {1969}, PAGES = {122--127}, ISSN = {0018-9448}, MRCLASS = {94.10}, MRNUMBER = {MR0242556 (39 \#3887)}, MRREVIEWER = {H. B. Mann}, } @book {Berlekamp68, AUTHOR = {Berlekamp, Elwyn R.}, TITLE = {Algebraic coding theory}, PUBLISHER = {McGraw-Hill Book Co.}, ADDRESS = {New York}, YEAR = {1968}, PAGES = {xiv+466}, MRCLASS = {94.10}, MRNUMBER = {MR0238597 (38 \#6873)}, MRREVIEWER = {M. A. Harrison}, } @article {ReedSo60, AUTHOR = {Reed, I. S. and Solomon, G.}, TITLE = {Polynomial codes over certain finite fields}, JOURNAL = {Journal of the Society of Industrial and Applied Mathematics}, VOLUME = {8}, YEAR = {1960}, PAGES = {300--304}, MRCLASS = {94.10}, MRNUMBER = {MR0127464 (23 \#B510)}, MRREVIEWER = {F. L. Bauer}, } @article {Reed54, AUTHOR = {Reed, Irving S.}, TITLE = {A class of multiple-error-correcting codes and the decoding scheme}, JOURNAL = {IRE Transactions on Information Theory}, VOLUME = {PGIT-4}, YEAR = {1954}, PAGES = {38--49}, MRCLASS = {94.0X}, MRNUMBER = {MR0089789 (19,721b)}, MRREVIEWER = {R. W. Hamming}, } @article{Muller54, AUTHOR = {Muller, D. E.}, TITLE = {Boolean algebras in electric circuit design}, JOURNAL = {The American Mathematical Monthly}, VOLUME = {61}, YEAR = {1954}, NUMBER = {7, part II}, PAGES = {27--28}, Note = {Proceedings of the symposium on special topics in applied mathematics, {N}orthwestern {U}niversity (1953)}, ISSN = {0002-9890}, MRCLASS = {78.0X}, MRNUMBER = {MR0063296 (16,99e)}, } @book {Sarnak90, AUTHOR = {Sarnak, Peter}, TITLE = {Some applications of modular forms}, SERIES = {Cambridge Tracts in Mathematics}, VOLUME = {99}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {1990}, PAGES = {x+111}, ISBN = {0-521-40245-6}, MRCLASS = {11F11 (05C35 11F30 11F37 11L05 22D40 28D05 68R10)}, MRNUMBER = {MR1102679 (92k:11045)}, MRREVIEWER = {Solomon Friedberg} } @article {CanettiEvGo95, AUTHOR = {Canetti, Ran and Even, Guy and Goldreich, Oded}, TITLE = {Lower bounds for sampling algorithms for estimating the average}, JOURNAL = {Information Processing Letters}, VOLUME = {53}, YEAR = {1995}, NUMBER = {1}, PAGES = {17--25}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {68Q25 (65C05)}, MRNUMBER = {MR1314708 (96e:68056)}, MRREVIEWER = {Stefan Heinrich}, } @article {BellareGoGo93, AUTHOR = {Bellare, Mihir and Goldreich, Oded and Goldwasser, Shafi}, TITLE = {Randomness in interactive proofs}, JOURNAL = {Computational Complexity}, VOLUME = {3}, YEAR = {1993}, NUMBER = {4}, PAGES = {319--354}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q10)}, MRNUMBER = {MR1262698 (96e:68029)}, } @BOOK{DubhashiPa09, AUTHOR = {Devdatt Dubhashi and Alessandro Panconesi}, OPTeditor = {}, TITLE = {Concentration of Measure for the Analysis of Randomized Algorithms}, PUBLISHER = {Cambridge University Press}, YEAR = {2009}, isbn = {ISBN-13: 9780521884273} } @article {BergerRo91, AUTHOR = {Berger, Bonnie and Rompel, John}, TITLE = {Simulating {$(\log\sp cn)$}-wise independence in {${\rm NC}$}}, JOURNAL = {Journal of the Association for Computing Machinery}, VOLUME = {38}, YEAR = {1991}, NUMBER = {4}, PAGES = {1026--1046}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68Q10 (68Q25 68R05)}, MRNUMBER = {MR1134525 (92k:68021)}, } @inproceedings{Pippenger85, author = {Nicholas Pippenger}, title = {On Networks of Noisy Gates}, booktitle = {FOCS}, year = {1985}, pages = {30-38}, crossref = {DBLP:conf/focs/FOCS26}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/FOCS26, title = {26th Annual Symposium on Foundations of Computer Science, 21-23 October 1985, Portland, Oregon, USA}, booktitle = {FOCS}, publisher = {IEEE}, year = {1985}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {FriedmanPi87, AUTHOR = {Friedman, J. and Pippenger, N.}, TITLE = {Expanding graphs contain all small trees}, JOURNAL = {Combinatorica}, VOLUME = {7}, YEAR = {1987}, NUMBER = {1}, PAGES = {71--76}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05C05 (05C35 05C55)}, MRNUMBER = {MR905153 (88k:05063)}, MRREVIEWER = {Yair Caro}, } @article {Dinur07, AUTHOR = {Dinur, Irit}, TITLE = {The {PCP} theorem by gap amplification}, JOURNAL = {Journal of the ACM}, VOLUME = {54}, YEAR = {2007}, NUMBER = {3}, PAGES = {article 12, 44 pages (electronic)}, ISSN = {0004-5411}, MRCLASS = {68Q15}, MRNUMBER = {MR2314254 (2008f:68037b)}, MRREVIEWER = {Frederic Green}, } @article {Berkowitz84, AUTHOR = {Berkowitz, Stuart J.}, TITLE = {On computing the determinant in small parallel time using a small number of processors}, JOURNAL = {Information Processing Letters}, VOLUME = {18}, YEAR = {1984}, NUMBER = {3}, PAGES = {147--150}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {65W05 (68Q15)}, MRNUMBER = {MR760366 (85k:65111)}, } @article {Strassen69, AUTHOR = {Strassen, Volker}, TITLE = {Gaussian elimination is not optimal}, JOURNAL = {Numerische Mathematik}, VOLUME = {13}, YEAR = {1969}, PAGES = {354--356}, ISSN = {0029-599X}, MRCLASS = {65.35}, MRNUMBER = {MR0248973 (40 \#2223)}, MRREVIEWER = {G. Fairweather}, } @inproceedings{Vazirani87, author = {Umesh V. Vazirani}, title = {Efficiency Considerations in Using Semi-random Sources (Extended Abstract)}, booktitle = {STOC}, year = {1987}, pages = {160-168}, crossref = {DBLP:conf/stoc/STOC19}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC19, title = {Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 25-27 May 1987, New York City, NY, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1987}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {Goldwasser09, AUTHOR = {Goldwasser, Shafi}, TITLE = {Cryptography without (hardly any) secrets?}, BOOKTITLE = {Advances in cryptology---{EUROCRYPT} 2009}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {5479}, PAGES = {369--370}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2009}, MRCLASS = {94A62}, MRNUMBER = {2538437}, DOI = {10.1007/978-3-642-01001-9_21}, URL = {http://dx.doi.org/10.1007/978-3-642-01001-9_21}, } @article {GoldwasserMiRa89, AUTHOR = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles}, TITLE = {The knowledge complexity of interactive proof systems}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {18}, YEAR = {1989}, NUMBER = {1}, PAGES = {186--208}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68T15 (03F07 68Q15 94A60)}, MRNUMBER = {MR978174 (90f:68157)}, MRREVIEWER = {Robert M. Baer}, } @article {BabaiMo88, AUTHOR = {Babai, L{\'a}szl{\'o} and Moran, Shlomo}, TITLE = {Arthur-{M}erlin games: a randomized proof system, and a hierarchy of complexity classes}, OPTNOTE = {17th Annual ACM Symposium on the Theory of Computing (Providence, RI, 1985)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {36}, YEAR = {1988}, NUMBER = {2}, PAGES = {254--276}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (03D15 05C25)}, MRNUMBER = {MR950433 (90b:68028)}, MRREVIEWER = {Jos{\'e} L. Balc{\'a}zar}, } @book {BurgisserClSh97, AUTHOR = {B{\"u}rgisser, Peter and Clausen, Michael and Shokrollahi, M. Amin}, TITLE = {Algebraic complexity theory}, SERIES = {Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]}, VOLUME = {315}, NOTE = {With the collaboration of Thomas Lickteig}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin}, YEAR = {1997}, PAGES = {xxiv+618}, ISBN = {3-540-60582-7}, MRCLASS = {68-02 (12Y05 65Y20 68Q05 68Q15 68Q25 68Q40)}, MRNUMBER = {MR1440179 (99c:68002)}, MRREVIEWER = {Alexander I. Barvinok}, } @article {Berlekamp70, AUTHOR = {Berlekamp, E. R.}, TITLE = {Factoring polynomials over large finite fields}, JOURNAL = {Mathematics of Computation}, VOLUME = {24}, YEAR = {1970}, PAGES = {713--735}, ISSN = {0025-5718}, MRCLASS = {12.25 (94.00)}, MRNUMBER = {MR0276200 (43 \#1948)}, MRREVIEWER = {C. G. Wagner}, } @incollection {KnuthYa76, AUTHOR = {Knuth, Donald E. and Yao, Andrew C.}, TITLE = {The complexity of nonuniform random number generation}, BOOKTITLE = {Algorithms and complexity ({P}roc. {S}ympos., {C}arnegie-{M}ellon {U}niv., {P}ittsburgh, {P}a., 1976)}, PAGES = {357--428}, PUBLISHER = {Academic Press}, ADDRESS = {New York}, YEAR = {1976}, MRCLASS = {65C10 (68A20)}, MRNUMBER = {MR0431601 (55 \#4598)}, MRREVIEWER = {George Marsaglia}, } @article {CoppersmithWi90, AUTHOR = {Coppersmith, Don and Winograd, Shmuel}, TITLE = {Matrix multiplication via arithmetic progressions}, JOURNAL = {Journal of Symbolic Computation}, VOLUME = {9}, YEAR = {1990}, NUMBER = {3}, PAGES = {251--280}, ISSN = {0747-7171}, MRCLASS = {68Q25 (11Y16 15A30)}, MRNUMBER = {MR1056627 (91i:68058)}, MRREVIEWER = {Werner Hartmann}, } @article {BunchHo74, AUTHOR = {Bunch, James R. and Hopcroft, John E.}, TITLE = {Triangular factorization and inversion by fast matrix multiplication}, JOURNAL = {Mathematics of Computation}, VOLUME = {28}, YEAR = {1974}, PAGES = {231--236}, ISSN = {0025-5718}, MRCLASS = {65F30}, MRNUMBER = {MR0331751 (48 \#10083)}, } @article {Csanky76, AUTHOR = {Csanky, L.}, TITLE = {Fast parallel matrix inversion algorithms}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {5}, YEAR = {1976}, NUMBER = {4}, PAGES = {618--623}, ISSN = {0097-5397}, MRCLASS = {65F05 (68A10)}, MRNUMBER = {MR0455310 (56 \#13549)}, MRREVIEWER = {Jo Ann Howell}, } @article {BorodinGaHo82, AUTHOR = {Borodin, Allan and von zur Gathen, Joachim and Hopcroft, John}, TITLE = {Fast parallel matrix and {GCD} computations}, JOURNAL = {Information and Control}, VOLUME = {52}, YEAR = {1982}, NUMBER = {3}, PAGES = {241--256}, ISSN = {0019-9958}, CODEN = {IFCNA4}, MRCLASS = {68C25 (10-04)}, MRNUMBER = {MR707576 (84j:68019)}, MRREVIEWER = {Joseph Ja'Ja'}, } @article {LevPiVa81, AUTHOR = {Lev, Gavriela Freund and Pippenger, Nicholas and Valiant, Leslie G.}, TITLE = {A fast parallel algorithm for routing in permutation networks}, JOURNAL = {IEEE Transactions on Computers}, VOLUME = {30}, YEAR = {1981}, NUMBER = {2}, PAGES = {93--100}, ISSN = {0018-9340}, CODEN = {ITCOB4}, MRCLASS = {68B20 (68C25 94C15)}, MRNUMBER = {MR605719 (82m:68055)} } @book {Goldreich10-prgprimer, AUTHOR = {Goldreich, Oded}, TITLE = {A primer on pseudorandom generators}, SERIES = {University Lecture Series}, VOLUME = {55}, PUBLISHER = {American Mathematical Society}, ADDRESS = {Providence, RI}, YEAR = {2010}, PAGES = {x+114}, ISBN = {978-0-8218-5192-0}, MRCLASS = {68-02 (68Q15 68Q17 68Q87 68W20)}, MRNUMBER = {2677397 (2011h:68001)}, MRREVIEWER = {Luis Hern{\'a}ndez Encinas}, } @article {BarnesBuRuSc98, AUTHOR = {Barnes, Greg and Buss, Jonathan F. and Ruzzo, Walter L. and Schieber, Baruch}, TITLE = {A sublinear space, polynomial time algorithm for directed {$s$}-{$t$} connectivity}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {27}, YEAR = {1998}, NUMBER = {5}, PAGES = {1273--1282 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68R10 (05C40 05C85 68Q25)}, MRNUMBER = {MR1623060 (99e:68117)}, MRREVIEWER = {Marek Kubale}, } @article {Valiant76, AUTHOR = {Valiant, Leslie G.}, TITLE = {Graph-theoretic properties in computational complexity}, OPTNOTE = {Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {13}, YEAR = {1976}, NUMBER = {3}, PAGES = {278--285}, ISSN = {0022-0000}, MRCLASS = {68A20}, MRNUMBER = {MR0441008 (55 \#13874)}, MRREVIEWER = {Zvi Galil}, } @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 = {MR697984 (85h:53029)}, MRREVIEWER = {Yu. Burago}, } @article {TaShma02, AUTHOR = {{Ta-S}hma, Amnon}, TITLE = {Storing information with extractors}, JOURNAL = {Information Processing Letters}, VOLUME = {83}, YEAR = {2002}, NUMBER = {5}, PAGES = {267--274}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {68P20 (68P10 68R10)}, MRNUMBER = {MR1910699 (2003d:68055)}, } @inproceedings{BatsonSpSr09, author = {Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava}, title = {Twice-ramanujan sparsifiers}, booktitle = {41st Annual ACM Symposium on Theory of Computing (Bethesda, MD)}, year = {2009}, pages = {255-262}, ee = {http://doi.acm.org/10.1145/1536414.1536451}, bibsource = {DBLP, http://dblp.uni-trier.de}, publisher = {ACM} } @InProceedings{CapalboReVaWi02, author={Michael Capalbo and Omer Reingold and Salil Vadhan and Avi Wigderson}, title={Randomness Conductors and Constant-Degree Lossless Expanders}, booktitle = "34th Annual ACM Symposium on Theory of Computing (STOC `02)", year = "2002", organization = "ACM", address = "Montr{\'e}al, CA", month = "May", note = {Joint session with {\em CCC `02}.}, pages = {659--668} } @inproceedings{AlonCa02, author = {Noga Alon and Michael R. Capalbo}, title = {Explicit Unique-Neighbor Expanders}, booktitle = {43rd Symposium on Foundations of Computer Science (Vancouver, BC, 2002)}, year = {2002}, pages = {73--79}, ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181884}, publisher = {IEEE} } @incollection {Cheeger70, AUTHOR = {Cheeger, Jeff}, TITLE = {A lower bound for the smallest eigenvalue of the {L}aplacian}, BOOKTITLE = {Problems in analysis ({P}apers dedicated to {S}alomon {B}ochner, 1969)}, PAGES = {195--199}, PUBLISHER = {Princeton Univ. Press}, ADDRESS = {Princeton, N. J.}, YEAR = {1970}, MRCLASS = {58G99 (53C20)}, MRNUMBER = {MR0402831 (53 \#6645)}, MRREVIEWER = {Harold Donnelly}, } @inproceedings{BenAroyaTa08, author = {Avraham {Ben-A}roya and Amnon {Ta-S}hma}, title = {A combinatorial construction of almost-{R}amanujan graphs using the zig-zag product}, booktitle = {40th Annual ACM Symposium on Theory of Computing (Victoria, British Columbia)}, year = {2008}, publisher = {ACM}, pages = {325-334}, ee = {http://doi.acm.org/10.1145/1374376.1374424}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{AlonCh88, AUTHOR = {Alon, N. and Chung, F. R. K.}, TITLE = {Explicit construction of linear sized tolerant networks}, Note = {Proceedings of the {F}irst {J}apan {C}onference on {G}raph {T}heory and {A}pplications ({H}akone, 1986)}, JOURNAL = {Discrete Mathematics}, VOLUME = {72}, YEAR = {1988}, NUMBER = {1-3}, PAGES = {15--19}, ISSN = {0012-365X}, CODEN = {DSMHA4}, MRCLASS = {05C38 (05C35 90B10)}, MRNUMBER = {MR975519 (90f:05080)}, } @article {ChungGrWi89, AUTHOR = {Chung, F. R. K. and Graham, R. L. and Wilson, R. M.}, TITLE = {Quasi-random graphs}, JOURNAL = {Combinatorica}, VOLUME = {9}, YEAR = {1989}, NUMBER = {4}, PAGES = {345--362}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05C80}, MRNUMBER = {MR1054011 (91e:05074)}, MRREVIEWER = {Zbigniew Palka}, } @article {ChungGr08, AUTHOR = {Chung, Fan and Graham, Ron}, TITLE = {Quasi-random graphs with given degree sequences}, JOURNAL = {Random Structures \& Algorithms}, VOLUME = {32}, YEAR = {2008}, NUMBER = {1}, PAGES = {1--19}, ISSN = {1042-9832}, MRCLASS = {05C80 (05C07 05C35 60C05)}, MRNUMBER = {MR2371048 (2009a:05189)}, MRREVIEWER = {Michael Krivelevich}, } @article {ChungGr02, AUTHOR = {Chung, Fan and Graham, Ronald}, TITLE = {Sparse quasi-random graphs}, NOTE = {Special issue: Paul Erd{\H{o}}s and his mathematics}, JOURNAL = {Combinatorica}, FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing}, VOLUME = {22}, YEAR = {2002}, NUMBER = {2}, PAGES = {217--244}, ISSN = {0209-9683}, MRCLASS = {05C35 (05C75 05C80)}, MRNUMBER = {MR1909084 (2003d:05110)}, MRREVIEWER = {A. G. Thomason}, } @article {BiluLi06, AUTHOR = {Bilu, Yonatan and Linial, Nathan}, TITLE = {Lifts, discrepancy and nearly optimal spectral gap}, JOURNAL = {Combinatorica}, VOLUME = {26}, YEAR = {2006}, NUMBER = {5}, PAGES = {495--519}, ISSN = {0209-9683}, MRCLASS = {05C50}, MRNUMBER = {MR2279667 (2008a:05160)}, MRREVIEWER = {Sebastian M. Cioab{\u{a}}}, } @article {Friedman08, AUTHOR = {Friedman, Joel}, TITLE = {A proof of {A}lon's second eigenvalue conjecture and related problems}, JOURNAL = {Memoirs of the American Mathematical Society}, VOLUME = {195}, YEAR = {2008}, NUMBER = {910}, PAGES = {viii+100}, ISSN = {0065-9266}, CODEN = {MAMCAU}, ISBN = {978-0-8218-4280-5}, MRCLASS = {68R10 (05C50 05C80)}, MRNUMBER = {MR2437174}, } @article{Margulis73, AUTHOR = {Margulis, G. 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, G. A.}, TITLE = {Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators}, JOURNAL = {Problemy Pereda{\v c}i Informacii}, FJOURNAL = {Akademiya Nauk SSSR. Institut Problem Peredachi Informatsii Akademii Nauk SSSR. Problemy Pereda{\v c}i Informacii}, 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}, } @incollection{Valiant77, AUTHOR = {Valiant, Leslie G.}, TITLE = {Graph-theoretic arguments in low-level complexity}, BOOKTITLE = {Mathematical foundations of computer science ({P}roc. {S}ixth {S}ympos., {T}atransk\'a {L}omnica, 1977)}, PAGES = {162--176. Lecture Notes in Comput. Sci., Vol. 53}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1977}, MRCLASS = {68A20}, MRNUMBER = {MR0660702 (58 \#32067)}, } @article{Urquhart87, AUTHOR = {Urquhart, Alasdair}, TITLE = {Hard examples for resolution}, JOURNAL = {J. Assoc. Comput. Mach.}, FJOURNAL = {Journal of the ACM}, 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}, } @article{Bassalygo81, author={Bassalygo, L. A.}, title={Asymptotically optimal switching circuits}, journal={Problems of Information Transmission}, volume={17}, year={1981}, number={3}, pages={206--211}, issn={0555-2923}, review={\MR{673739 (83j:94031)}} } @book {CormenLeRiSt01, AUTHOR = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford}, TITLE = {Introduction to algorithms}, EDITION = {Second}, PUBLISHER = {MIT Press}, ADDRESS = {Cambridge, MA}, YEAR = {2001}, PAGES = {xxii+1180}, ISBN = {0-262-03293-7}, MRCLASS = {68-01 (05-01 05C85 68P05 68P10 68Q25 68Wxx)}, MRNUMBER = {MR1848805 (2002e:68001)}, } @incollection {LewinVa98, AUTHOR = {Lewin, Daniel and Vadhan, Salil}, TITLE = {Checking polynomial identities over any field: towards a derandomization?}, BOOKTITLE = {30th Annual ACM Symposium on the Theory of Computing ({D}allas, {TX})}, PAGES = {438--447}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {1999}, MRCLASS = {68W30 (12Y05)}, MRNUMBER = {MR1731594}, } @article {Erdos47, AUTHOR = {Erd{\H o}s, P.}, TITLE = {Some remarks on the theory of graphs}, JOURNAL = {Bulletin of the American Mathematical Society}, VOLUME = {53}, YEAR = {1947}, PAGES = {292--294}, ISSN = {0002-9904}, MRCLASS = {56.0X}, MRNUMBER = {MR0019911 (8,479d)}, MRREVIEWER = {H. S. M. Coxeter}, } @book {Artin91, AUTHOR = {Artin, Michael}, TITLE = {Algebra}, PUBLISHER = {Prentice Hall Inc.}, ADDRESS = {Englewood Cliffs, NJ}, YEAR = {1991}, PAGES = {xviii+618}, ISBN = {0-13-004763-5}, MRCLASS = {00A05 (11-01 12-01 13-01 15-01 16-01 20-01)}, MRNUMBER = {MR1129886 (92g:00001)}, MRREVIEWER = {Gerald J. Janusz}, } @book {LidlPi98, AUTHOR = {Lidl, Rudolf and Pilz, G{\"u}nter}, TITLE = {Applied abstract algebra}, SERIES = {Undergraduate Texts in Mathematics}, EDITION = {Second}, PUBLISHER = {Springer-Verlag}, ADDRESS = {New York}, YEAR = {1998}, PAGES = {xvi+486}, ISBN = {0-387-98290-6}, MRCLASS = {00A05 (11T71 68-01 68P25 68Q40 94A60)}, MRNUMBER = {MR1485777 (98m:00002)}, } @book {LidlNi94, AUTHOR = {Lidl, Rudolf and Niederreiter, Harald}, TITLE = {Introduction to finite fields and their applications}, EDITION = {first}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {1994}, PAGES = {xii+416}, ISBN = {0-521-46094-8}, MRCLASS = {11Txx (94A60 94B27)}, MRNUMBER = {MR1294139 (95f:11098)}, } @article {Gromov03, AUTHOR = {Gromov, M.}, TITLE = {Random walk in random groups}, JOURNAL = {Geometric and Functional Analysis}, VOLUME = {13}, YEAR = {2003}, NUMBER = {1}, PAGES = {73--146}, ISSN = {1016-443X}, CODEN = {GFANFB}, MRCLASS = {20F65 (20F67 20P05 60G50)}, MRNUMBER = {MR1978492 (2004j:20088a)}, MRREVIEWER = {Thomas Delzant}, } @article{Guruswami04, author = {Venkatesan Guruswami}, title = {Guest column: error-correcting codes and expander graphs}, journal = {SIGACT News}, volume = {35}, number = {3}, year = {2004}, pages = {25-41}, ee = {http://doi.acm.org/10.1145/1027914.1027924}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {ArmoniTaWiZh00, AUTHOR = {Armoni, Roy and {Ta-S}hma, Amnon and Wigderson, Avi and Zhou, Shiyu}, TITLE = {An {$O(\log(n)\sp {4/3})$} space algorithm for {$(s,t)$} connectivity in undirected graphs}, JOURNAL = {Journal of the ACM}, VOLUME = {47}, YEAR = {2000}, NUMBER = {2}, PAGES = {294--311}, ISSN = {0004-5411}, MRCLASS = {68R10 (05C40 05C85 68Q25)}, MRNUMBER = {MR1769444 (2001c:68098)}, } @incollection {Armoni98, AUTHOR = {Armoni, Roy}, TITLE = {On the derandomization of space-bounded computations}, BOOKTITLE = {Randomization and approximation techniques in computer science ({B}arcelona, 1998)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {1518}, PAGES = {47--59}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1998}, MRCLASS = {68Q05 (68Q15 68W20)}, MRNUMBER = {MR1729161 (2000k:68048)}, } @article {BuhrmanMiRaVe02, AUTHOR = {Buhrman, H. and Miltersen, P. B. and Radhakrishnan, J. and Venkatesh, S.}, TITLE = {Are bitvectors optimal?}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {31}, YEAR = {2002}, NUMBER = {6}, PAGES = {1723--1744 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68P10 (68P05 68P20)}, MRNUMBER = {MR1954872 (2004a:68014)}, } @article {MartinRa06, AUTHOR = {Martin, Russell and Randall, Dana}, TITLE = {Disjoint decomposition of {M}arkov chains and sampling circuits in {C}ayley graphs}, JOURNAL = {Combinatorics, Probability and Computing}, VOLUME = {15}, YEAR = {2006}, NUMBER = {3}, PAGES = {411--448}, ISSN = {0963-5483}, MRCLASS = {60J10 (05C25)}, MRNUMBER = {MR2216477 (2007f:60056)}, MRREVIEWER = {Pavel T. Stoynov}, } @incollection {MartinRa00, AUTHOR = {Martin, Russell A. and Randall, Dana}, TITLE = {Sampling adsorbing staircase walks using a new {M}arkov chain decomposition method}, BOOKTITLE = {41st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience ({R}edondo {B}each, {CA}, 2000)}, PAGES = {492--502}, PUBLISHER = {IEEE Comput. Soc. Press}, ADDRESS = {Los Alamitos, CA}, YEAR = {2000}, MRCLASS = {68Q99 (60J10)}, MRNUMBER = {MR1931846}, } @article {AlonScSh08, AUTHOR = {Alon, Noga and Schwartz, Oded and Shapira, Asaf}, TITLE = {An elementary construction of constant-degree expanders}, JOURNAL = {Combinatorics, Probability and Computing}, VOLUME = {17}, YEAR = {2008}, NUMBER = {3}, PAGES = {319--327}, ISSN = {0963-5483}, MRCLASS = {05C07 (05C50 68R10)}, MRNUMBER = {MR2410389}, } @article {AlonRo94, AUTHOR = {Alon, Noga and Roichman, Yuval}, TITLE = {Random {C}ayley graphs and expanders}, JOURNAL = {Random Structures \& Algorithms}, VOLUME = {5}, YEAR = {1994}, NUMBER = {2}, PAGES = {271--284}, ISSN = {1042-9832}, MRCLASS = {05C50 (05C25 05C80)}, MRNUMBER = {MR1262979 (94k:05132)}, MRREVIEWER = {Joseph B. Klerlein}, } @article {AlonGaMi87, AUTHOR = {Alon, N. and Galil, Z. and Milman, V. 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 = {MR905991 (89f:68023)}, } @article {Alon86a, AUTHOR = {Alon, N.}, TITLE = {Eigenvalues and expanders}, NOTE = {Theory of computing (Singer Island, Fla., 1984)}, JOURNAL = {Combinatorica}, FJOURNAL = {Combinatorica. An International Journal of the J\'anos Bolyai Mathematical Society}, VOLUME = {6}, YEAR = {1986}, NUMBER = {2}, PAGES = {83--96}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05C50}, MRNUMBER = {MR875835 (88e:05077)}, MRREVIEWER = {Claude Benzaken}, } @article {Alon86b, AUTHOR = {Alon, N.}, TITLE = {Eigenvalues, geometric expanders, sorting in rounds, and {R}amsey theory}, JOURNAL = {Combinatorica}, FJOURNAL = {Combinatorica. An International Journal of the J\'anos Bolyai Mathematical Society}, VOLUME = {6}, YEAR = {1986}, NUMBER = {3}, PAGES = {207--219}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {05C55 (05B05 68R10)}, MRNUMBER = {MR875289 (88g:05090)}, MRREVIEWER = {Pavol Hell}, } @article {SaksZh99, AUTHOR = {Saks, Michael and Zhou, Shiyu}, TITLE = {{${\rm BP}\sb {\rm H}{\rm SPACE}(S)\subseteq{\rm DSPACE}(S\sp {3/2})$}}, OPTNOTE = {36th IEEE Symposium on the Foundations of Computer Science (Milwaukee, WI, 1995)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {58}, YEAR = {1999}, NUMBER = {2}, PAGES = {376--403}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (68Q25 68W20)}, MRNUMBER = {MR1696012 (2000d:68053)}, } @book {Lubotzky94, AUTHOR = {Lubotzky, Alexander}, TITLE = {Discrete groups, expanding graphs and invariant measures}, SERIES = {Progress in Mathematics}, VOLUME = {125}, NOTE = {With an appendix by Jonathan D. Rogawski}, PUBLISHER = {Birkh\"auser Verlag}, ADDRESS = {Basel}, YEAR = {1994}, PAGES = {xii+195}, ISBN = {3-7643-5075-X}, MRCLASS = {22E40 (05C25 11F70 28C10 43A07)}, MRNUMBER = {MR1308046 (96g:22018)}, MRREVIEWER = {Wolfgang Woess}, } @incollection {Lubtozky95, AUTHOR = {Lubotzky, Alexander}, TITLE = {Cayley graphs: eigenvalues, expanders and random walks}, BOOKTITLE = {Surveys in combinatorics, 1995 ({S}tirling)}, SERIES = {London Math. Soc. Lecture Note Ser.}, VOLUME = {218}, PAGES = {155--189}, PUBLISHER = {Cambridge Univ. Press}, ADDRESS = {Cambridge}, YEAR = {1995}, MRCLASS = {05C25 (15A18 60J15 68R10)}, MRNUMBER = {MR1358635 (96k:05081)}, MRREVIEWER = {Daniel Ashlock}, } @book {DavidoffSaVa03, AUTHOR = {Davidoff, Giuliana and Sarnak, Peter and Valette, Alain}, TITLE = {Elementary number theory, group theory, and {R}amanujan graphs}, SERIES = {London Mathematical Society Student Texts}, VOLUME = {55}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2003}, PAGES = {x+144}, ISBN = {0-521-82426-5; 0-521-53143-8}, MRCLASS = {11-01 (05C75 11E25 20G05 20G40)}, MRNUMBER = {MR1989434 (2004f:11001)}, MRREVIEWER = {Thomas R. Shemanske}, } @incollection {BosleyDo07, AUTHOR = {Bosley, Carl and Dodis, Yevgeniy}, TITLE = {Does privacy require true randomness?}, BOOKTITLE = {Theory of cryptography}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {4392}, PAGES = {1--20}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2007}, MRCLASS = {94A60}, MRNUMBER = {2444592 (2009f:94032)}, MRREVIEWER = {Herv{\'e} P. J. Chabanne}, DOI = {10.1007/978-3-540-70936-7_1}, URL = {http://dx.doi.org/10.1007/978-3-540-70936-7_1}, } @ARTICLE{ReingoldVaWi01, author = {Omer Reingold and Salil Vadhan and Avi Wigderson}, title = {Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders}, journal = {Annals of Mathematics}, year = {2001}, volume = {155}, number = {1}, OPTpages = {}, month = {January}, OPTnote = {}, OPTkey = {}, OPTcrossref = {}, OPTannote = {}, } @INPROCEEDINGS{RozenmanVa05, AUTHOR = "Eyal Rozenman and Salil Vadhan", TITLE = "Derandomized Squaring of Graphs", BOOKTITLE = "Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM `05)", YEAR = "2005", OPTeditor = "", OPTvolume = "", number = "3624", series = "Lecture Notes in Computer Science", pages = "436--447", address = "Berkeley, CA", month = "August", OPTorganization = "", publisher = "Springer", OPTabstract = "", OPTkeywords = "", OPTfile = F } @article {Healy08, AUTHOR = {Healy, Alexander D.}, TITLE = {Randomness-efficient sampling within {${\rm NC}\sp 1$}}, JOURNAL = {Computational Complexity}, VOLUME = {17}, YEAR = {2008}, NUMBER = {1}, PAGES = {3--37}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q10 68R10)}, MRNUMBER = {MR2402893}, } @article {Kahale97, AUTHOR = {Kahale, Nabil}, TITLE = {Large deviation bounds for {M}arkov chains}, JOURNAL = {Combinatorics, Probability and Computing}, VOLUME = {6}, YEAR = {1997}, NUMBER = {4}, PAGES = {465--474}, ISSN = {0963-5483}, MRCLASS = {60J10 (60F10)}, MRNUMBER = {MR1483429 (98g:60120)}, } @article {Kahale95, AUTHOR = {Kahale, Nabil}, TITLE = {Eigenvalues and expansion of regular graphs}, JOURNAL = {Journal of the ACM}, VOLUME = {42}, YEAR = {1995}, NUMBER = {5}, PAGES = {1091--1106}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68R10 (05C50 68Q25)}, MRNUMBER = {MR1412045 (97f:68149)}, } @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} } @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 = {J. Assoc. Comput. Mach.}, FJOURNAL = {Journal of the ACM}, 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} } @incollection {GoldreichImLeVeZu90, AUTHOR = {Goldreich, Oded and Impagliazzo, Russell and Levin, Leonid and Venkatesan, Ramarathnam and Zuckerman, David}, TITLE = {Security preserving amplification of hardness}, BOOKTITLE = {31st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, {V}ol.\ {I}, {II} ({S}t.\ {L}ouis, {MO}, 1990)}, PAGES = {318--326}, PUBLISHER = {IEEE Comput. Soc. Press}, ADDRESS = {Los Alamitos, CA}, YEAR = {1990}, MRCLASS = {94A60 (68P25)}, MRNUMBER = {MR1150704 (92k:94017)}, } @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}, NOTE = {Codes and complexity}, JOURNAL = {IEEE Trans. Inform. Theory}, FJOURNAL = {Institute of Electrical and Electronics Engineers. 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}, NOTE = {Codes and complexity}, JOURNAL = {IEEE Trans. Inform. Theory}, FJOURNAL = {Institute of Electrical and Electronics Engineers. 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}, } @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} } @InProceedings{AlonMi84, title={Eigenvalues, Expanders and Superconcentrators (Extended Abstract)}, author={Alon, Noga and Milman, V. 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, A. and Phillips, R. and Sarnak, P.}, 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, M.}, 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, N. and Milman, V. D.}, TITLE = {$\lambda\sb 1,$ isoperimetric inequalities for graphs, and superconcentrators}, FJOURNAL = {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 = {} } @InProceedings{BroderSh87, 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} } @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}, } @incollection {Hoffman70, AUTHOR = {Hoffman, Alan J.}, TITLE = {On eigenvalues and colorings of graphs}, BOOKTITLE = {Graph {T}heory and its {A}pplications ({P}roc. {A}dvanced {S}em., {M}ath. {R}esearch {C}enter, {U}niv. of {W}isconsin, {M}adison, {W}is., 1969)}, PAGES = {79--91}, PUBLISHER = {Academic Press}, ADDRESS = {New York}, YEAR = {1970}, MRCLASS = {05.55}, MRNUMBER = {MR0284373 (44 \#1601)}, MRREVIEWER = {R. C. Read}, } @article {Joffe74, AUTHOR = {Joffe, A.}, TITLE = {On a set of almost deterministic {$k$}-independent random variables}, JOURNAL = {Annals of Probability}, VOLUME = {2}, YEAR = {1974}, NUMBER = {1}, PAGES = {161--162}, MRCLASS = {60A05}, MRNUMBER = {MR0356150 (50 \#8621)}, MRREVIEWER = {W. A. Woyczynski}, } @article {Joffe71, AUTHOR = {Joffe, A.}, TITLE = {On a sequence of almost deterministic pairwise independent random variables}, JOURNAL = {Proceedings of the American Mathematical Society}, VOLUME = {29}, YEAR = {1971}, PAGES = {381--382}, ISSN = {0002-9939}, MRCLASS = {60.20}, MRNUMBER = {MR0279857 (43 \#5578)}, MRREVIEWER = {A. Mukherjea}, } @article {WegmanCa79, AUTHOR = {Wegman, Mark N. and Carter, J. Lawrence}, TITLE = {New hash functions and their use in authentication and set equality}, OPTNOTE = {Special issue dedicated to Michael Machtey}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {22}, YEAR = {1981}, NUMBER = {3}, PAGES = {265--279}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68B15}, MRNUMBER = {MR633535 (82i:68017)}, } @inproceedings{Pippenger79, author = {Nicholas Pippenger}, title = {On Simultaneous Resource Bounds (Preliminary Version)}, booktitle = {20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico)}, year = {1979}, pages = {307-311}, publisher = {IEEE}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {AlonMaSz99, AUTHOR = {Alon, Noga and Matias, Yossi and Szegedy, Mario}, TITLE = {The space complexity of approximating the frequency moments}, OPTNOTE = {Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {58}, YEAR = {1999}, NUMBER = {1, part 2}, PAGES = {137--147}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q25 (68W20)}, MRNUMBER = {MR1688610 (2000h:68087)}, MRREVIEWER = {Hsien-Kuei Hwang}, } @article{ErdosFrFu85, AUTHOR = {Erd{\H{o}}s, P. and Frankl, P. and F{\"u}redi, Z.}, TITLE = {Families of finite sets in which no set is covered by the union of {$r$} others}, JOURNAL = {Israel Journal of Mathematics}, VOLUME = {51}, YEAR = {1985}, NUMBER = {1-2}, PAGES = {79--89}, ISSN = {0021-2172}, CODEN = {ISJMAP}, MRCLASS = {05A05 (05B07)}, MRNUMBER = {MR804477 (87a:05008)}, MRREVIEWER = {Noga Alon}, } @article{Sipser88, AUTHOR = {Sipser, Michael}, TITLE = {Expanders, randomness, or time versus space}, NOTE = {Structure in Complexity Theory Conference (Berkeley, CA, 1986)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {36}, YEAR = {1988}, NUMBER = {3}, PAGES = {379--383}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (05C99)}, MRNUMBER = {MR973446 (90e:68038)}, MRREVIEWER = {William Gasarch}, } @article {Lancaster65, AUTHOR = {Lancaster, H. O.}, TITLE = {Pairwise statistical independence}, JOURNAL = {Annals of Mathematical Statistics}, VOLUME = {36}, YEAR = {1965}, PAGES = {1313--1317}, ISSN = {0003-4851}, MRCLASS = {60.10 (60.20)}, MRNUMBER = {MR0176507 (31 \#779)}, MRREVIEWER = {R. F. Gundy}, } @article {Luby93, AUTHOR = {Luby, Michael}, TITLE = {Removing randomness in parallel computation without a processor penalty}, OPTNOTE = {29th Annual IEEE Symposium on Foundations of Computer Science (White Plains, NY, 1988)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {47}, YEAR = {1993}, NUMBER = {2}, PAGES = {250--286}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q22 (68Q20 68Q55)}, MRNUMBER = {MR1246178 (94k:68085)}, MRREVIEWER = {Julian Padget}, } @article {FredmanKoSz84, AUTHOR = {Fredman, Michael L. and Koml{\'o}s, J{\'a}nos and Szemer{\'e}di, Endre}, TITLE = {Storing a sparse table with {$O(1)$} worst case access time}, JOURNAL = {Journal of the ACM}, VOLUME = {31}, YEAR = {1984}, NUMBER = {3}, PAGES = {538--544}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68P05}, MRNUMBER = {MR819156}, } @article {ChorGo89, AUTHOR = {Chor, Benny and Goldreich, Oded}, TITLE = {On the power of two-point based sampling}, JOURNAL = {Journal of Complexity}, VOLUME = {5}, YEAR = {1989}, NUMBER = {1}, PAGES = {96--106}, ISSN = {0885-064X}, MRCLASS = {68Q25}, MRNUMBER = {MR990814 (90g:68059)}, } @article {CarterWe79, AUTHOR = {Carter, J. Lawrence and Wegman, Mark N.}, TITLE = {Universal classes of hash functions}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {18}, YEAR = {1979}, NUMBER = {2}, PAGES = {143--154}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68H05 (68C25)}, MRNUMBER = {MR532173 (80f:68110a)}, } @article {Raghavan88, AUTHOR = {Raghavan, Prabhakar}, TITLE = {Probabilistic construction of deterministic algorithms: approximating packing integer programs}, NOTE = {Twenty-Seventh Annual IEEE Symposium on the Foundations of Computer Science (Toronto, ON, 1986)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {37}, YEAR = {1988}, NUMBER = {2}, PAGES = {130--143}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {90C10 (90C09)}, MRNUMBER = {MR979115 (90a:90134)}, MRREVIEWER = {Klaus Hofstedt}, } @book {Spencer94, AUTHOR = {Spencer, Joel}, TITLE = {Ten lectures on the probabilistic method}, SERIES = {CBMS-NSF Regional Conference Series in Applied Mathematics}, VOLUME = {64}, EDITION = {Second}, PUBLISHER = {Society for Industrial and Applied Mathematics (SIAM)}, ADDRESS = {Philadelphia, PA}, YEAR = {1994}, PAGES = {vi+88}, ISBN = {0-89871-325-0}, MRCLASS = {05C80 (05C55 60C05)}, MRNUMBER = {MR1249485 (95c:05113)}, MRREVIEWER = {Andrzej Ruci{\'n}ski}, } @article {ErdosSe73, AUTHOR = {Erd{\H{o}}s, P. and Selfridge, J. L.}, TITLE = {On a combinatorial game}, JOURNAL = {Journal of Combinatorial Theory. Series A}, VOLUME = {14}, YEAR = {1973}, PAGES = {298--301}, MRCLASS = {90D05 (05A05)}, MRNUMBER = {MR0327313 (48 \#5655)}, MRREVIEWER = {R. K. Guy}, } @article {Luby86, AUTHOR = {Luby, Michael}, TITLE = {A simple parallel algorithm for the maximal independent set problem}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {15}, YEAR = {1986}, NUMBER = {4}, PAGES = {1036--1053}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68Q20 (05C35 68R05)}, MRNUMBER = {MR861369 (87m:68030)}, } @incollection {BuhrmanFo99, AUTHOR = {Buhrman, Harry and Fortnow, Lance}, TITLE = {One-sided two-sided error in probabilistic computation}, BOOKTITLE = {STACS 99 (Trier)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {1563}, PAGES = {100--109}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1999}, MRCLASS = {68Q15}, MRNUMBER = {MR1734040 (2000i:68056)}, } @InCollection{Vadhan00-pcmi, author = {Salil Vadhan}, title = {Probabilistic Proof Systems, Part {I} --- Interactive \& Zero-Knowledge Proofs}, booktitle = {Computational Complexity Theory}, OPTcrossref = {}, OPTkey = {}, publisher = {American Mathematical Society}, year = {2004}, editor = {S. Rudich and A. Wigderson}, volume = {10}, OPTnumber = {}, series = {IAS/Park City Mathematics Series}, OPTchapter = {}, OPTtype = {}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, pages = {315--348}, OPTannote = {} } @article {GoldreichMiWi91, AUTHOR = {Goldreich, Oded and Micali, Silvio and Wigderson, Avi}, TITLE = {Proofs that yield nothing but their validity, or {A}ll languages in {NP} have zero-knowledge proof systems}, JOURNAL = {Journal of the ACM}, VOLUME = {38}, YEAR = {1991}, NUMBER = {3}, PAGES = {691--729}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68Q15 (68P25 94A60)}, MRNUMBER = {MR1125927 (93b:68025)}, MRREVIEWER = {Joan Boyar}, } @InProceedings{ReingoldTrVa06, author = {Omer Reingold and Luca Trevisan and Salil Vadhan}, title = {Pseudorandom Walks in Regular Digraphs and the \mbox{RL} vs.\ \mbox{L} Problem}, BOOKTITLE = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC `06)}, PAGES = {457--466}, MONTH = {21--23 May}, c-address = {Seattle, WA}, year = {2006}, note = {Preliminary version as {\em ECCC} TR05-22, February 2005.} } @article {Nisan94, AUTHOR = {Nisan, Noam}, TITLE = {{${\rm RL}\subseteq {\rm SC}$}}, JOURNAL = {Computational Complexity}, VOLUME = {4}, YEAR = {1994}, NUMBER = {1}, PAGES = {1--11}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q10)}, MRNUMBER = {1272773 (96a:68037)}, DOI = {10.1007/BF01205052}, URL = {http://dx.doi.org/10.1007/BF01205052}, } @article {Nisan92, AUTHOR = {Nisan, Noam}, TITLE = {Pseudorandom generators for space-bounded computation}, JOURNAL = {Combinatorica}, VOLUME = {12}, YEAR = {1992}, NUMBER = {4}, PAGES = {449--461}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68Q15 (65C10 65Y20)}, MRNUMBER = {MR1194735 (94c:68073)}, MRREVIEWER = {Wen Qi Huang}, } @article {Nisan91, AUTHOR = {Nisan, Noam}, TITLE = {Pseudorandom bits for constant depth circuits}, JOURNAL = {Combinatorica}, VOLUME = {11}, YEAR = {1991}, NUMBER = {1}, PAGES = {63--70}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68Q15 (03D15 68Q25)}, MRNUMBER = {MR1112275 (92g:68055)}, } @incollection {Adleman78, AUTHOR = {Adleman, Leonard}, TITLE = {Two theorems on random polynomial time}, BOOKTITLE = {19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich., 1978)}, PAGES = {75--83}, PUBLISHER = {IEEE}, ADDRESS = {Long Beach, Calif.}, YEAR = {1978}, MRCLASS = {68C25}, MRNUMBER = {MR539832 (80e:68095)}, } @book {AroraBa09, AUTHOR = {Arora, Sanjeev and Barak, Boaz}, TITLE = {Computational complexity}, NOTE = {A modern approach}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2009}, PAGES = {xxiv+579}, ISBN = {978-0-521-42426-4}, MRCLASS = {68-01 (03D15 41A99 68Q15 68Q17 68Q25 81P68 94A60)}, MRNUMBER = {MR2500087}, } @book {Goldreich08, AUTHOR = {Goldreich, Oded}, TITLE = {Computational complexity: a conceptual perspective}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2008}, PAGES = {xxiv+606}, ISBN = {978-0-521-88473-0}, MRCLASS = {68-01 (68Q15 68Q17 68Q25 94A60 94A62)}, MRNUMBER = {MR2400985}, } @article {HartmanisSt65, AUTHOR = {Hartmanis, J. and Stearns, R. E.}, TITLE = {On the computational complexity of algorithms}, JOURNAL = {Transactions of the American Mathematical Society}, VOLUME = {117}, YEAR = {1965}, PAGES = {285--306}, ISSN = {0002-9947}, MRCLASS = {02.80}, MRNUMBER = {MR0170805 (30 \#1040)}, MRREVIEWER = {Walter Oberschelp}, } @article {Lautemann83, AUTHOR = {Lautemann, Clemens}, TITLE = {B{PP} and the polynomial hierarchy}, JOURNAL = {Information Processing Letters}, VOLUME = {17}, YEAR = {1983}, NUMBER = {4}, PAGES = {215--217}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {03D15 (68Q05 68Q15)}, MRNUMBER = {MR742072 (85j:03063)}, } @inproceedings {LachishRa01, AUTHOR = {Lachish, Oded and Raz, Ran}, TITLE = {Explicit lower bound of {$4.5n-o(n)$} for {B}oolean circuits}, BOOKTITLE = {33rd Annual ACM Symposium on Theory of Computing}, PAGES = {399--408 (electronic)}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2001}, MRCLASS = {68Q17}, MRNUMBER = {MR2120340}, } @incollection {IwamaMo02, AUTHOR = {Iwama, Kazuo and Morizumi, Hiroki}, TITLE = {An explicit lower bound of {$5n-o(n)$} for {B}oolean circuits}, BOOKTITLE = {Mathematical foundations of computer science 2002}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {2420}, PAGES = {353--364}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2002}, MRCLASS = {68Q17 (94C10)}, MRNUMBER = {MR2064471}, } @inproceedings{Mihail89, author = {Milena Mihail}, title = {Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders}, booktitle = {30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, North Carolina)}, year = {1989}, pages = {526-531}, publisher = {IEEE}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {SahniGo76, AUTHOR = {Sahni, Sartaj and Gonzalez, Teofilo}, TITLE = {{$P$}-complete approximation problems}, JOURNAL = {Journal of the ACM}, VOLUME = {23}, YEAR = {1976}, NUMBER = {3}, PAGES = {555--565}, ISSN = {0004-5411}, MRCLASS = {68A20}, MRNUMBER = {MR0408313 (53 \#12078)}, MRREVIEWER = {M. Manas}, } @inproceedings{Spielman07, author = {Daniel A. Spielman}, title = {Spectral Graph Theory and its Applications}, booktitle = {48th Symposium on Foundations of Computer Science (FOCS 2007), 21-23 October 2007, Providence, RI, USA, Proceedings}, year = {2007}, pages = {29--38} } @article {AlonSu00, AUTHOR = {Alon, Noga and Sudakov, Benny}, TITLE = {Bipartite subgraphs and the smallest eigenvalue}, JOURNAL = {Combinatorics, Probability and Computing}, VOLUME = {9}, YEAR = {2000}, NUMBER = {1}, PAGES = {1--12}, ISSN = {0963-5483}, MRCLASS = {05C50}, MRNUMBER = {MR1751298 (2001e:05077)}, MRREVIEWER = {Kevin Lawrence McAvaney}, } @book {Lovasz07, AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o}}, TITLE = {Combinatorial problems and exercises}, EDITION = {second}, PUBLISHER = {AMS Chelsea Publishing, Providence, RI}, YEAR = {2007}, PAGES = {642}, ISBN = {978-0-8218-4262-1}, MRCLASS = {05-01}, MRNUMBER = {MR2321240}, } @article {Fill91, AUTHOR = {Fill, James Allen}, TITLE = {Eigenvalue bounds on convergence to stationarity for nonreversible {M}arkov chains, with an application to the exclusion process}, JOURNAL = {Annals of Applied Probability}, VOLUME = {1}, YEAR = {1991}, NUMBER = {1}, PAGES = {62--87}, ISSN = {1050-5164}, MRCLASS = {60J10 (60K35)}, MRNUMBER = {MR1097464 (92h:60104)}, MRREVIEWER = {Gregory F. Lawler}, } @article {KahnLiNiSa89, AUTHOR = {Kahn, Jeff D. and Linial, Nathan and Nisan, Noam and Saks, Michael E.}, TITLE = {On the cover time of random walks on graphs}, JOURNAL = {Journal of Theoretical Probability}, VOLUME = {2}, YEAR = {1989}, NUMBER = {1}, PAGES = {121--128}, ISSN = {0894-9840}, CODEN = {JTPREO}, MRCLASS = {60J10 (05C99)}, MRNUMBER = {MR981769 (90b:60080)}, MRREVIEWER = {David J. Aldous}, } @article {CoppersmithFeSh96, AUTHOR = {Coppersmith, Don and Feige, Uriel and Shearer, James}, TITLE = {Random walks on regular and irregular graphs}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {9}, YEAR = {1996}, NUMBER = {2}, PAGES = {301--308}, ISSN = {0895-4801}, CODEN = {SJDMEC}, MRCLASS = {05C99 (60J15 68R10)}, MRNUMBER = {MR1386885 (97d:05263)}, MRREVIEWER = {Walter M. B{\"o}hm}, } @article {BrightwellWi90, AUTHOR = {Brightwell, Graham and Winkler, Peter}, TITLE = {Maximum hitting time for random walks on graphs}, JOURNAL = {Random Structures \& Algorithms}, VOLUME = {1}, YEAR = {1990}, NUMBER = {3}, PAGES = {263--276}, ISSN = {1042-9832}, MRCLASS = {60J15 (60C05)}, MRNUMBER = {MR1099792 (92e:60134)}, MRREVIEWER = {Jos{\'e} L. Palacios}, } @article {Savitch70, AUTHOR = {Savitch, Walter J.}, TITLE = {Relationships between nondeterministic and deterministic tape complexities}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {4}, YEAR = {1970}, PAGES = {177--192}, ISSN = {0022-0000}, MRCLASS = {94.40}, MRNUMBER = {MR0266702 (42 \#1605)}, MRREVIEWER = {H. Maurer}, } @article {GoemansWi95, AUTHOR = {Goemans, Michel X. and Williamson, David P.}, TITLE = {Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming}, JOURNAL = {Journal of the ACM}, VOLUME = {42}, YEAR = {1995}, NUMBER = {6}, PAGES = {1115--1145}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {90C27 (68Q25 90C35)}, MRNUMBER = {MR1412228 (97g:90108)}, MRREVIEWER = {Nikolay N. Ivanov}, } @incollection{JerrumSi96, AUTHOR = "Mark Jerrum and Alistair Sinclair", editor = "D.S. Hochbaum", TITLE = "The {M}arkov Chain {M}onte {C}arlo Method: an Approach to Approximate Counting and Integration", BOOKTITLE = "Approximation Algorithms for NP-hard Problems", CHAPTER = "12", pages = "482--520", PUBLISHER = "PWS Publishing", YEAR = "1996" } @inproceedings{Randall03, author = {Dana Randall}, title = {Mixing}, booktitle = {44th Symposium on Foundations of Computer Science (Cambridge, MA)}, year = {2003}, pages = {4--15}, ee = {http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400004abs.htm}, publisher = {IEEE Computer Society}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {EvenSeYa84, AUTHOR = {Even, Shimon and Selman, Alan L. and Yacobi, Yacov}, TITLE = {The complexity of promise problems with applications to public-key cryptography}, JOURNAL = {Information and Control}, VOLUME = {61}, YEAR = {1984}, NUMBER = {2}, PAGES = {159--173}, ISSN = {0019-9958}, CODEN = {IFCNA4}, MRCLASS = {94A60 (68P25)}, MRNUMBER = {MR772678 (86e:94018)}, MRREVIEWER = {Evangelos Kranakis}, } @incollection {Goldreich06, AUTHOR = {Goldreich, Oded}, TITLE = {On promise problems: a survey}, BOOKTITLE = {Theoretical computer science}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {3895}, PAGES = {254--290}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2006}, MRCLASS = {68Q15}, MRNUMBER = {MR2248667 (2007f:68058)}, } @article {GoldreichGoRo98, AUTHOR = {Goldreich, Oded and Goldwasser, Shafi and Ron, Dana}, TITLE = {Property testing and its connection to learning and approximation}, JOURNAL = {Journal of the ACM}, VOLUME = {45}, YEAR = {1998}, NUMBER = {4}, PAGES = {653--750}, ISSN = {0004-5411}, MRCLASS = {68Q25 (05C85 60C05 68R10 68W25)}, MRNUMBER = {1675099 (2000d:68059)}, MRREVIEWER = {Mark R. Jerrum}, DOI = {10.1145/285055.285060}, URL = {http://dx.doi.org/10.1145/285055.285060}, } @article {RubinfeldSu96, AUTHOR = {Rubinfeld, Ronitt and Sudan, Madhu}, TITLE = {Robust characterizations of polynomials with applications to program testing}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {25}, YEAR = {1996}, NUMBER = {2}, PAGES = {252--271}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68Q25 (68Q60)}, MRNUMBER = {1379300 (97h:68050)}, MRREVIEWER = {Claus-Peter Schnorr}, DOI = {10.1137/S0097539793255151}, URL = {http://dx.doi.org/10.1137/S0097539793255151}, } @incollection {Ron01, AUTHOR = {Ron, Dana}, TITLE = {Property testing}, BOOKTITLE = {Handbook of randomized computing, Vol. I, II}, SERIES = {Comb. Optim.}, VOLUME = {9}, PAGES = {597--649}, PUBLISHER = {Kluwer Acad. Publ.}, ADDRESS = {Dordrecht}, YEAR = {2001}, MRCLASS = {68W25 (05C75 68Q15 68Q17 68Q32 68R10 68W20)}, MRNUMBER = {MR1966913 (2004c:68161)}, } @article {BlumLuRu93, AUTHOR = {Blum, Manuel and Luby, Michael and Rubinfeld, Ronitt}, TITLE = {Self-testing/correcting with applications to numerical problems}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {47}, YEAR = {1993}, NUMBER = {3}, PAGES = {549--595}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {65C20}, MRNUMBER = {1248868 (94m:65020)}, MRREVIEWER = {Joseph Kreimer}, DOI = {10.1016/0022-0000(93)90044-W}, URL = {http://dx.doi.org/10.1016/0022-0000(93)90044-W}, } @incollection {Rubinfeld06, AUTHOR = {Rubinfeld, Ronitt}, TITLE = {Sublinear time algorithms}, BOOKTITLE = {International Congress of Mathematicians. Vol. III}, PAGES = {1095--1110}, PUBLISHER = {Eur. Math. Soc., Z\"urich}, YEAR = {2006}, MRCLASS = {68Q25 (68W20 68W25)}, MRNUMBER = {MR2275720 (2007m:68124)}, MRREVIEWER = {Eldar Fischer}, } @article {Hoeffding63, AUTHOR = {Hoeffding, Wassily}, TITLE = {Probability inequalities for sums of bounded random variables}, JOURNAL = {Journal of the American Statistical Association}, VOLUME = {58}, YEAR = {1963}, PAGES = {13--30}, ISSN = {0162-1459}, MRCLASS = {60.20}, MRNUMBER = {MR0144363 (26 \#1908)}, MRREVIEWER = {E. H. Lehman, Jr.}, } @article {Chernoff52, AUTHOR = {Chernoff, Herman}, TITLE = {A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations}, JOURNAL = {Annals of Mathematical Statistics}, VOLUME = {23}, YEAR = {1952}, PAGES = {493--507}, ISSN = {0003-4851}, MRCLASS = {62.0X}, MRNUMBER = {MR0057518 (15,241c)}, MRREVIEWER = {H. Teicher}, } @article {Gill77, AUTHOR = {Gill, John}, TITLE = {Computational complexity of probabilistic {T}uring machines}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {6}, YEAR = {1977}, NUMBER = {4}, PAGES = {675--695}, ISSN = {1095-7111}, MRCLASS = {68A20 (94A35)}, MRNUMBER = {MR0464691 (57 \#4616)}, MRREVIEWER = {A. L. Selman} } @book {Leighton92, AUTHOR = {Leighton, F. Thomson}, TITLE = {Introduction to parallel algorithms and architectures: arrays, trees, and hypercubes}, OPTNOTE = {Arrays, trees, hypercubes}, PUBLISHER = {Morgan Kaufmann}, ADDRESS = {San Mateo, CA}, YEAR = {1992}, PAGES = {xx+831}, ISBN = {1-55860-117-1}, MRCLASS = {68Q22 (05C85 68-02 68R10)}, MRNUMBER = {MR1137272 (92j:68041)}, MRREVIEWER = {Julian Padget}, } @inproceedings{Harvey06, author = {Nicholas J. A. Harvey}, title = {Algebraic Structures and Algorithms for Matching and Matroid Problems}, booktitle = {47th Annual IEEE Symposium on Foundations of Computer Science (Berkeley, CA)}, year = {2006}, pages = {531-542}, ee = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.8}, publisher = {IEEE}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{MuchaSa04, author = {Marcin Mucha and Piotr Sankowski}, title = {Maximum Matchings via Gaussian Elimination}, booktitle = {45th Symposium on Foundations of Computer Science (Rome, Italy)}, year = {2004}, pages = {248-255}, ee = {http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280248abs.htm}, publisher = {IEEE Computer Society}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {MulmuleyVaVa87, AUTHOR = {Mulmuley, Ketan and Vazirani, Umesh V. and Vazirani, Vijay V.}, TITLE = {Matching is as easy as matrix inversion}, JOURNAL = {Combinatorica}, VOLUME = {7}, YEAR = {1987}, NUMBER = {1}, PAGES = {105--113}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68Q20 (05C70 68R10 90B10)}, MRNUMBER = {MR905157 (89a:68092)}, MRREVIEWER = {Joseph Ja'Ja'}, } @inproceedings{Zippel79, author = {Richard Zippel}, title = {Probabilistic algorithms for sparse polynomials}, booktitle = {EUROSAM}, year = {1979}, pages = {216-226}, crossref = {DBLP:conf/eurosam/1979}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/eurosam/1979, editor = {Edward W. Ng}, title = {Symbolic and Algebraic Computation, EUROSAM '79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings}, booktitle = {EUROSAM}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {72}, year = {1979}, isbn = {3-540-09519-5}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Schwartz80, AUTHOR = {Schwartz, Jacob T.}, TITLE = {Fast probabilistic algorithms for verification of polynomial identities}, JOURNAL = {Journal of the ACM}, VOLUME = {27}, YEAR = {1980}, NUMBER = {4}, PAGES = {701--717}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68C20 (03B35 12-04)}, MRNUMBER = {MR594695 (82m:68078)}, } @article{DeMilloLi78, author = {Richard A. DeMillo and Richard J. Lipton}, title = {A Probabilistic Remark on Algebraic Program Testing}, journal = {Information Processing Letters}, volume = {7}, number = {4}, year = {1978}, pages = {193-195}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {KarpUpWi86, AUTHOR = {Karp, R. M. and Upfal, E. and Wigderson, A.}, TITLE = {Constructing a perfect matching is in {R}andom {NC}}, JOURNAL = {Combinatorica}, VOLUME = {6}, YEAR = {1986}, NUMBER = {1}, PAGES = {35--48}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68Q15 (05-04 05C70 68Q25 68R10)}, MRNUMBER = {MR856642 (88c:68038)}, MRREVIEWER = {T. R. S. Walsh}, } @article {DvirSh06, AUTHOR = {Dvir, Zeev and Shpilka, Amir}, TITLE = {Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2006/07}, NUMBER = {5}, PAGES = {1404--1434 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q25 (11T71 94B65)}, MRNUMBER = {MR2284088}, } @article {KayalSa07, AUTHOR = {Kayal, Neeraj and Saxena, Nitin}, TITLE = {Polynomial identity testing for depth 3 circuits}, JOURNAL = {Computational Complexity}, VOLUME = {16}, YEAR = {2007}, NUMBER = {2}, PAGES = {115--138}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (94C05)}, MRNUMBER = {MR2318254}, } @article {Johnson72, AUTHOR = {Johnson, Selmer}, TITLE = {Upper bounds for constant weight error correcting codes}, JOURNAL = {Discrete Mathematics}, VOLUME = {3}, YEAR = {1972}, PAGES = {109--124}, ISSN = {0012-365X}, MRCLASS = {94A10}, MRNUMBER = {0379001 (51 \#15167)}, MRREVIEWER = {N. J. A. Sloane}, } @article {Johnson71, AUTHOR = {Johnson, Selmer M.}, TITLE = {On upper bounds for unrestricted binary error-correcting codes}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {IT-17}, YEAR = {1971}, PAGES = {466--478}, ISSN = {0018-9448}, MRCLASS = {94A10}, MRNUMBER = {0337426 (49 \#2195)}, MRREVIEWER = {L. D. Rudolph}, } @article {Johnson63, AUTHOR = {Johnson, Selmer M.}, TITLE = {Improved asymptotic bounds for error-correcting codes}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {IT-9}, YEAR = {1963}, PAGES = {198--205}, ISSN = {0018-9448}, MRCLASS = {94.10}, MRNUMBER = {MR0163789 (29 \#1089)}, MRREVIEWER = {W. W. Peterson}, } @article {Johnson62, AUTHOR = {Johnson, Selmer M.}, TITLE = {A new upper bound for error-correcting codes}, JOURNAL = {IRE Transactions on Information Theory}, VOLUME = {IT-8}, YEAR = {1962}, PAGES = {203--207}, MRCLASS = {94.10}, MRNUMBER = {MR0137615 (25 \#1067)}, MRREVIEWER = {E. C. Posner}, } @article {Peterson60, AUTHOR = {Peterson, W. W.}, TITLE = {Encoding and error-correction procedures for the {B}ose-{C}haudhuri codes. }, JOURNAL = {IRE Transactions on Information Theory}, VOLUME = {IT-6}, YEAR = {1960}, PAGES = {459--470}, MRCLASS = {94.00}, MRNUMBER = {MR0118576 (22 \#9349)}, MRREVIEWER = {R. W. Hamming}, } @ARTICLE{Wozencraft58, AUTHOR = "J.M. Wozencraft", TITLE = "List decoding", JOURNAL = "Quarterly Progress Report, Research Laboratory of Electronics, MIT", YEAR = "1958", volume = "48", pages = "90--95", file = F } @book {Elias57, AUTHOR = {Elias, Peter}, TITLE = {List decoding for noisy channels}, PUBLISHER = {Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, Mass., Rep. No. 335}, YEAR = {1957}, PAGES = {12}, MRCLASS = {94.00}, MRNUMBER = {MR0099261 (20 \#5702)}, MRREVIEWER = {R. W. Hamming}, } @article {Shannon48, AUTHOR = {Shannon, C. E.}, TITLE = {A mathematical theory of communication}, JOURNAL = {The Bell System Technical Journal}, VOLUME = {27}, YEAR = {1948}, PAGES = {379--423, 623--656}, ISSN = {0005-8580}, MRCLASS = {60.0X}, MRNUMBER = {MR0026286 (10,133e)}, MRREVIEWER = {J. L. Doob}, } @article {Hamming50, AUTHOR = {Hamming, R. W.}, TITLE = {Error detecting and error correcting codes}, JOURNAL = {The Bell System Technical Journal}, VOLUME = {29}, YEAR = {1950}, PAGES = {147--160}, ISSN = {0005-8580}, MRCLASS = {60.0X}, MRNUMBER = {MR0035935 (12,35c)}, MRREVIEWER = {H. H. Goldstine}, } @article {Elias91, AUTHOR = {Elias, Peter}, TITLE = {Error-correcting codes for list decoding}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {37}, YEAR = {1991}, NUMBER = {1}, PAGES = {5--12}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B35}, MRNUMBER = {MR1087881 (91j:94026)}, DOI = {10.1109/18.61123}, URL = {http://dx.doi.org/10.1109/18.61123}, } @MISC{Sudan04, author = "Madhu Sudan", title = "Essential Coding Theory (Lecture Notes)", howpublished = "\url{http://people.csail.mit.edu/madhu/FT04/}", year = "2004", file = F } @book {MacWilliamsSl77, AUTHOR = {MacWilliams, F. J. and Sloane, N. J. A.}, TITLE = {The theory of error-correcting codes.}, NOTE = {North-Holland Mathematical Library, Vol. 16}, PUBLISHER = {North-Holland Publishing Co.}, ADDRESS = {Amsterdam}, YEAR = {1977}, MRCLASS = {94A10}, MRNUMBER = {MR0465510 (57 \#5408b)}, MRREVIEWER = {Ian Blake}, } @InProceedings{Pinsker73, author = {M. 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{BarakRaShWi12, author = {Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi}, title = {2-source dispersers for $n^{o(1)}$ entropy and {R}amsey graphs beating the {F}rankl-{W}ilson construction}, journal = {Annals of Mathematics}, year = {2012}, OPTvolume = {}, OPTnumber = {}, OPTpages = {}, OPTmonth = {}, note = {To appear. Preliminary version in {\em STOC `06}}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @inproceedings {BarakRaShWi06-old, AUTHOR = {Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi}, TITLE = {2-source dispersers for sub-polynomial entropy and {R}amsey graphs beating the {F}rankl-{W}ilson construction}, BOOKTITLE = {STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing}, PAGES = {671--680}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2006}, MRCLASS = {68R10 (05C55 68W20)}, MRNUMBER = {MR2277192 (2007h:68151)}, } @inproceedings {KatzTr00, AUTHOR = {Katz, Jonathan and Trevisan, Luca}, TITLE = {On the efficiency of local decoding procedures for error-correcting codes}, BOOKTITLE = {Proceedings of the {T}hirty-{S}econd {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {80--86 (electronic)}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2000}, MRCLASS = {68Q25 (94B99)}, MRNUMBER = {2114520}, DOI = {10.1145/335305.335315}, URL = {http://dx.doi.org/10.1145/335305.335315}, } @book {KatzLi08, AUTHOR = {Katz, Jonathan and Lindell, Yehuda}, TITLE = {Introduction to modern cryptography}, SERIES = {Chapman \& Hall/CRC Cryptography and Network Security}, PUBLISHER = {Chapman \& Hall/CRC, Boca Raton, FL}, YEAR = {2008}, PAGES = {xviii+534}, ISBN = {978-1-58488-551-1; 1-58488-551-3}, MRCLASS = {94A60 (11T71 94-01)}, MRNUMBER = {MR2371431 (2009b:94051)}, MRREVIEWER = {Steven D. Galbraith}, } @book {Goldreich04, AUTHOR = {Goldreich, Oded}, TITLE = {Foundations of cryptography. {II}}, NOTE = {Basic Applications}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2004}, PAGES = {i--xxii and 373--798}, ISBN = {0-521-83084-2}, MRCLASS = {94A60 (94-01)}, MRNUMBER = {MR2061203 (2005i:94008)}, MRREVIEWER = {Simon R. Blackburn}, } @book {Goldreich01, AUTHOR = {Goldreich, Oded}, TITLE = {Foundations of cryptography}, NOTE = {Basic tools}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2001}, PAGES = {xx+372}, ISBN = {0-521-79172-3}, MRCLASS = {94A60 (68-01 68P25 94-01)}, MRNUMBER = {MR1881185 (2004a:94042)}, } @article {Chung89, AUTHOR = {Chung, F. R. K.}, TITLE = {Diameters and eigenvalues}, JOURNAL = {Journal of the American Mathematical Society}, VOLUME = {2}, YEAR = {1989}, NUMBER = {2}, PAGES = {187--196}, ISSN = {0894-0347}, MRCLASS = {05C50 (05C38)}, MRNUMBER = {MR965008 (89k:05070)}, MRREVIEWER = {Ralph Faudree} } @article {Lovasz79-Shannon, AUTHOR = {Lov{\'a}sz, L{\'a}szl{\'o}}, TITLE = {On the {S}hannon capacity of a graph}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {25}, YEAR = {1979}, NUMBER = {1}, PAGES = {1--7}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {05C99 (94A17)}, MRNUMBER = {MR514926 (81g:05095)}, } @book {Stichtenoth09, AUTHOR = {Stichtenoth, Henning}, TITLE = {Algebraic function fields and codes}, SERIES = {Graduate Texts in Mathematics}, VOLUME = {254}, EDITION = {Second}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin}, YEAR = {2009}, PAGES = {xiv+355}, ISBN = {978-3-540-76877-7}, MRCLASS = {14H05 (11R58 11T71 14G15 14G50 94B27)}, MRNUMBER = {2464941 (2010d:14034)}, } @inproceedings{Agrawal03, author = {Manindra Agrawal}, title = {On Derandomizing Tests for Certain Polynomial Identities}, booktitle = {IEEE Conference on Computational Complexity}, year = {2003}, pages = {355-}, ee = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214434}, crossref = {DBLP:conf/coco/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/coco/2003, title = {18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark}, booktitle = {IEEE Conference on Computational Complexity}, publisher = {IEEE Computer Society}, year = {2003}, isbn = {0-7695-1879-6}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{Lovasz79, author = {L{\'a}szl{\'o} Lov{\'a}sz}, title = {On determinants, matchings, and random algorithms.}, booktitle = {Fundamentals of Computation Theory (Berlin/Wendisch-Rietz)}, year = {1979}, pages = {565-574}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {Reingold08, AUTHOR = {Reingold, Omer}, TITLE = {Undirected connectivity in log-space}, JOURNAL = {Journal of the ACM}, VOLUME = {55}, YEAR = {2008}, NUMBER = {4}, PAGES = {Art. 17, 24}, ISSN = {0004-5411}, MRCLASS = {68Q25}, MRNUMBER = {MR2445014}, } @incollection {AleliunasKaLiLoRa79, AUTHOR = {Aleliunas, Romas and Karp, Richard M. and Lipton, Richard J. and Lov{\'a}sz, L{\'a}szl{\'o} and Rackoff, Charles}, TITLE = {Random walks, universal traversal sequences, and the complexity of maze problems}, BOOKTITLE = {20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979)}, PAGES = {218--223}, PUBLISHER = {IEEE}, ADDRESS = {New York}, YEAR = {1979}, MRCLASS = {68E10 (68C25 90C35)}, MRNUMBER = {MR598110 (82h:68084)}, } @inproceedings{Broder86, author = {Andrei Z. Broder}, title = {How hard is to marry at random? (On the approximation of the permanent)}, booktitle = {18th Annual ACM Symposium on Theory of Computing (Berkeley, CA),}, year = {1986}, publisher = {ACM}, pages = {50-58}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {JerrumSiVi04, AUTHOR = {Jerrum, Mark and Sinclair, Alistair and Vigoda, Eric}, TITLE = {A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries}, JOURNAL = {Journal of the ACM}, VOLUME = {51}, YEAR = {2004}, NUMBER = {4}, PAGES = {671--697 (electronic)}, ISSN = {0004-5411}, MRCLASS = {15A15 (68W25)}, MRNUMBER = {MR2147852 (2006b:15013)}, MRREVIEWER = {Ravindra B. Bapat}, } @article {AgrawalBi03, AUTHOR = {Agrawal, Manindra and Biswas, Somenath}, TITLE = {Primality and identity testing via {C}hinese remaindering}, JOURNAL = {Journal of the ACM}, VOLUME = {50}, YEAR = {2003}, NUMBER = {4}, PAGES = {429--443 (electronic)}, ISSN = {0004-5411}, MRCLASS = {68Q25 (11Y11 68Q15)}, MRNUMBER = {MR2146881 (2006b:68043)}, } @article {AgrawalKaSa04, AUTHOR = {Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin}, TITLE = {P{RIMES} is in {P}}, JOURNAL = {Annals of Mathematics. Second Series}, VOLUME = {160}, YEAR = {2004}, NUMBER = {2}, PAGES = {781--793}, ISSN = {0003-486X}, CODEN = {ANMAAH}, MRCLASS = {11Y11 (11A51 68Q15 68Q25)}, MRNUMBER = {MR2123939 (2006a:11170)}, MRREVIEWER = {Carl Pomerance}, } @book {MitzenmacherUp05, AUTHOR = {Mitzenmacher, Michael and Upfal, Eli}, TITLE = {Probability and computing}, NOTE = {Randomized algorithms and probabilistic analysis}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {2005}, PAGES = {xvi+352}, ISBN = {0-521-83540-2}, MRCLASS = {68-01 (60C05 60G42 60J10 60J25 60K25 68W20 68W40)}, MRNUMBER = {MR2144605 (2006d:68002)}, MRREVIEWER = {Mark R. Jerrum}, } @book {MotwaniRa95, AUTHOR = {Motwani, Rajeev and Raghavan, Prabhakar}, TITLE = {Randomized algorithms}, PUBLISHER = {Cambridge University Press}, ADDRESS = {Cambridge}, YEAR = {1995}, PAGES = {xiv+476}, ISBN = {0-521-47465-5}, MRCLASS = {65Cxx (60G42 60J20 65Yxx 68Q25)}, MRNUMBER = {MR1344451 (96i:65003)}, MRREVIEWER = {Mark R. Jerrum}, } @article {Gillman98, AUTHOR = {Gillman, David}, TITLE = {A {C}hernoff bound for random walks on expander graphs}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {27}, YEAR = {1998}, NUMBER = {4}, PAGES = {1203--1220 (electronic)}, ISSN = {0097-5397}, MRCLASS = {60F10 (60J10 68Q25)}, MRNUMBER = {MR1621958 (99e:60076)}, MRREVIEWER = {Mark R. Jerrum}, } @INBOOK{Miltersen01, AUTHOR = {{Peter Bro} Miltersen}, OPTeditor = {}, TITLE = {Handbook of Randomized Computing}, CHAPTER = {Derandomizing Complexity Classes}, OPTpages = {}, PUBLISHER = {Kluwer}, YEAR = {2001} } @ARTICLE{Trevisan04, AUTHOR = {Luca Trevisan}, JOURNAL = {Quaderni di Matematica}, TITLE = {Some Applications of Coding Theory in Computational Complexity}, YEAR = {2004}, volume = {13}, OPTnumber = {}, pages = {347--424} } @ARTICLE{Sudan00, AUTHOR = {Madhu Sudan}, TITLE = {List decoding: Algorithms and applications}, JOURNAL = {SIGACT News}, YEAR = {2000}, volume = {31}, number = {1}, pages = {16--27} } @article{Kabanets02-old, author = {Valentine Kabanets}, title = {Derandomization: a brief overview.}, journal = {Bulletin of the EATCS}, volume = {76}, year = {2002}, pages = {88-103}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {Santhanam07, AUTHOR = {Santhanam, Rahul}, TITLE = {Circuit lower bounds for {M}erlin-{A}rthur classes}, BOOKTITLE = {S{TOC}'07---{P}roceedings of the 39th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing}, PAGES = {275--283}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {2007}, MRCLASS = {68Q17}, MRNUMBER = {2402451 (2009e:68040)}, DOI = {10.1145/1250790.1250832}, URL = {http://dx.doi.org/10.1145/1250790.1250832}, } @article {TaShmaZuSa06, AUTHOR = {Ta-Shma, Amnon and Zuckerman, David and Safra, Shmuel}, TITLE = {Extractors from {R}eed-{M}uller codes}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {72}, YEAR = {2006}, NUMBER = {5}, PAGES = {786--812}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {94B27 (68W99)}, MRNUMBER = {2228126 (2007k:94104)}, DOI = {10.1016/j.jcss.2005.05.010}, URL = {http://dx.doi.org/10.1016/j.jcss.2005.05.010}, } @article {TaShmaZu04, AUTHOR = {{Ta-S}hma, Amnon and Zuckerman, David}, TITLE = {Extractor codes}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {50}, YEAR = {2004}, NUMBER = {12}, PAGES = {3015--3025}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B60 (94A40)}, MRNUMBER = {MR2103480 (2005f:94170)}, } @article {GalvinTe06, AUTHOR = {Galvin, David and Tetali, Prasad}, TITLE = {Slow mixing of {G}lauber dynamics for the hard-core model on regular bipartite graphs}, JOURNAL = {Random Structures \& Algorithms}, VOLUME = {28}, YEAR = {2006}, NUMBER = {4}, PAGES = {427--443}, ISSN = {1042-9832}, MRCLASS = {05C80 (60C05)}, MRNUMBER = {MR2225701 (2007a:05127)}, MRREVIEWER = {Hai Yan Chen}, } @article {GuruswamiRu08, AUTHOR = {Guruswami, Venkatesan and Rudra, Atri}, TITLE = {Explicit codes achieving list decoding capacity: error-correction with optimal redundancy}, JOURNAL = {IEEE Transactions on Information Theory}, VOLUME = {54}, YEAR = {2008}, NUMBER = {1}, PAGES = {135--150}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {94B35 (94A24)}, MRNUMBER = {MR2446745 (2010b:94096)}, MRREVIEWER = {Landang Yuan}, DOI = {10.1109/TIT.2007.911222}, URL = {http://dx.doi.org/10.1109/TIT.2007.911222}, } @inproceedings{ParvareshVa05, author = {Farzad Parvaresh and Alexander Vardy}, title = {Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time.}, booktitle = focs05, year = {2005}, pages = {285-294}, ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.29}, crossref = {DBLP:conf/focs/2005}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/2005, title = {46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings}, booktitle = {FOCS}, publisher = {IEEE Computer Society}, year = {2005}, isbn = {0-7695-2468-0}, bibsource = {DBLP, http://dblp.uni-trier.de} } @InProceedings{ReingoldVaWi00-old, author = "Omer Reingold and Salil Vadhan and Avi Wigderson", title = "Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors", OPTcrossref = "", OPTkey = "", OPTeditor = "", OPTvolume = "", OPTnumber = "", OPTseries = "", pages = "3--13", booktitle = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS `00)}, year = 2000, organization = {IEEE}, OPTpublisher = "", address = {Redondo Beach, CA}, month = {17--19 } # oct, note = "", OPTannote = "" } @article{Kopparty12, author = {Swastik Kopparty}, title = {List-Decoding Multiplicity Codes}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {19}, year = {2012}, pages = {44}, ee = {http://eccc.hpi-web.de/report/2012/044}, bibsource = {DBLP, http://dblp.uni-trier.de} } @inproceedings{KoppartySaYe11, author = {Swastik Kopparty and Shubhangi Saraf and Sergey Yekhanin}, title = {High-rate codes with sublinear-time decoding}, booktitle = {STOC}, year = {2011}, pages = {167-176}, ee = {http://doi.acm.org/10.1145/1993636.1993660}, crossref = {DBLP:conf/stoc/2011}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/2011, editor = {Lance Fortnow and Salil P. Vadhan}, title = {Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011}, booktitle = {STOC}, publisher = {ACM}, year = {2011}, isbn = {978-1-4503-0691-1}, bibsource = {DBLP, http://dblp.uni-trier.de} } @incollection {DvirKoSaSu09, AUTHOR = {Dvir, Zeev and Kopparty, Swastik and Saraf, Shubhangi and Sudan, Madhu}, TITLE = {Extensions to the method of multiplicities, with applications to {K}akeya sets and mergers}, BOOKTITLE = {2009 50th {A}nnual {IEEE} {S}ymposium on {F}oundations of {C}omputer {S}cience ({FOCS} 2009)}, PAGES = {181--190}, PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA}, YEAR = {2009}, MRCLASS = {68R05 (68Q87)}, MRNUMBER = {2648400 (2011d:68128)}, DOI = {10.1109/FOCS.2009.40}, URL = {http://dx.doi.org/10.1109/FOCS.2009.40}, } @ARTICLE{GuruswamiUmVa09, AUTHOR = "Venkatesan Guruswami and Christopher Umans and Salil Vadhan", TITLE = "Unbalanced Expanders and Randomness Extractors from {P}arvaresh--{V}ardy Codes", JOURNAL = {Journal of the ACM}, YEAR = {2009}, volume = {56}, number = {4}, pages = {1--34}, OPTmonth = {}, OPTnote = {Preliminary version recipient of Best Paper Award at {\em CCC `07}.}, OPTabstract = {}, OPTkeywords = {}, OPTgrants = {NSF CCF-0133096, ONR N00014-04-1-0478, BSF 2002246, a Guggenheim Fellowship, and the Miller Institute for Basic Research in Science}, OPTharvardaddendum = {waiverfiled} } @INPROCEEDINGS{VadhanZh12, AUTHOR = {Salil Vadhan and Colin Jia Zheng}, TITLE = {Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions}, BOOKTITLE = {Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC `12)}, OPTnote = {Full version posted as {\em ECCC} TR11-141}, pages = {817-836}, MONTH = {19--22 May}, c-address = {New York, NY}, year = {2012}, OPTgrants = {NSF grant CCF-1116616, US-Israel BSF grant 2010196, MSR, Stanford}, harvard-addendum = {waiver} } @INPROCEEDINGS{HaitnerReVa10, AUTHOR = {Iftach Haitner and Omer Reingold and Salil Vadhan}, TITLE = {Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions}, BOOKTITLE = {Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC `10)}, OPTnote = {Accepted to {\em SIAM J. Computing} Special Issue on STOC `10 (pending minor revisions)}, PAGES = {437--446}, MONTH = {6--8 June}, c-address = {Cambridge, MA}, year = {2010}, OPTgrants = {NSF grant CNS-0831289 and US-Israel BSF grant 2006060}, OPTdoi = {http://dx.doi.org/10.1145/1806689.1806750}, OPTharvard-addendum = {waiver} } @inproceedings{LuReVaWi03, author = {Chi-Jen Lu and Omer Reingold and Salil Vadhan and Avi Wigderson}, title = {Extractors: optimal up to constant factors}, booktitle = {Proceedings of the 35th ACM Symposium on Theory of Computing (STOC `03)}, year = {2003}, isbn = {1-58113-674-9}, pages = {602--611}, location = {San Diego, CA, USA}, doi = {http://doi.acm.org/10.1145/780542.780630}, organization = {ACM}, } @article {TaShmaUmZu07, AUTHOR = {{Ta-S}hma, Amnon and Umans, Christopher and Zuckerman, David}, TITLE = {Lossless condensers, unbalanced expanders, and extractors}, JOURNAL = {Combinatorica}, VOLUME = {27}, YEAR = {2007}, NUMBER = {2}, PAGES = {213--240}, ISSN = {0209-9683}, MRCLASS = {68Q01 (68R10 68W20)}, MRNUMBER = {2321925 (2008g:68020)}, MRREVIEWER = {Heng Liang}, DOI = {10.1007/s00493-007-0053-2}, URL = {http://dx.doi.org/10.1007/s00493-007-0053-2}, } @article {SchmidtSiSr95, AUTHOR = {Schmidt, Jeanette P. and Siegel, Alan and Srinivasan, Aravind}, TITLE = {Chernoff-{H}oeffding bounds for applications with limited independence}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {8}, YEAR = {1995}, NUMBER = {2}, PAGES = {223--250}, ISSN = {0895-4801}, CODEN = {SJDMEC}, MRCLASS = {60E15 (60F10 60G50)}, MRNUMBER = {MR1329508 (96c:60022)}, MRREVIEWER = {Dominik Szynal}, } @article{Goldreich97, author = {Oded Goldreich}, title = {A Sample of Samplers - A Computational Perspective on Sampling (survey).}, journal = {Electronic Colloquium on Computational Complexity (ECCC)}, volume = {4}, number = {20}, year = {1997}, ee = {http://eccc.hpi-web.de/eccc-reports/1997/TR97-020/index.html}, bibsource = {DBLP, http://dblp.uni-trier.de} } @Article{HooryLiWi06, author={Shlomo Hoory and Nathan Linial and Avi Wigderson}, title={Expander graphs and their applications}, journal={Bulletin of the AMS}, volume={43}, number={4}, pages={439-561}, year={2006}, } @incollection {GuruswamiWa11, AUTHOR = {Guruswami, Venkatesan and Wang, Carol}, TITLE = {Optimal rate list decoding via derivative codes}, BOOKTITLE = {Approximation, randomization, and combinatorial optimization}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {6845}, PAGES = {593--604}, PUBLISHER = {Springer}, ADDRESS = {Heidelberg}, YEAR = {2011}, MRCLASS = {94B35}, MRNUMBER = {2863293}, DOI = {10.1007/978-3-642-22935-0_50}, URL = {http://dx.doi.org/10.1007/978-3-642-22935-0_50}, } @BOOK{Guruswami06, AUTHOR = {Venkatesan Guruswami}, OPTeditor = {}, TITLE = {Algorithmic Results in List Decoding}, PUBLISHER = {now publishers}, YEAR = {2006}, volume = {2, number 2}, OPTnumber = {2}, series = {Foundations and Trends in Theoretical Computer Science} } @BOOK{Muthukrishnan05, AUTHOR = {S. Muthukrishnan}, OPTeditor = {}, TITLE = {Data Streams: Algorithms and Applications}, PUBLISHER = {now publishers}, YEAR = {2005}, volume = {1, number 2}, OPTnumber = {2}, series = {Foundations and Trends in Theoretical Computer Science} } @BOOK{LubyWi05, AUTHOR = {Michael Luby and Avi Wigderson}, OPTeditor = {}, TITLE = {Pairwise Independence and Derandomization}, PUBLISHER = {now publishers}, YEAR = {2005}, volume = {1, number 4}, OPTnumber = {4}, series = {Foundations and Trends in Theoretical Computer Science} } @article {ReingoldShWi06, AUTHOR = {Reingold, Omer and Shaltiel, Ronen and Wigderson, Avi}, TITLE = {Extracting randomness via repeated condensing}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {35}, YEAR = {2006}, NUMBER = {5}, PAGES = {1185--1209 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q99 (68R05 68W20)}, MRNUMBER = {2217142 (2006m:68110)}, MRREVIEWER = {Bogdan S. Chlebus}, DOI = {10.1137/S0097539703431032}, URL = {http://dx.doi.org/10.1137/S0097539703431032}, } @incollection {RazRe99, AUTHOR = {Raz, Ran and Reingold, Omer}, TITLE = {On recycling the randomness of states in space bounded computation}, BOOKTITLE = {Annual {ACM} {S}ymposium on {T}heory of {C}omputing ({A}tlanta, {GA}, 1999)}, PAGES = {159--168 (electronic)}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {1999}, MRCLASS = {68W20 (68Q05 68Q15)}, MRNUMBER = {1797474 (2001i:68168)}, DOI = {10.1145/301250.301294}, URL = {http://dx.doi.org/10.1145/301250.301294}, } @ARTICLE{Vadhan04, AUTHOR = "Salil P. Vadhan", TITLE = "Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model", JOURNAL = "Journal of Cryptology", YEAR = "2004", volume = "17", number = "1", pages = "43--77", month = "January", OPTnote = "Extended abstract in {\em CRYPTO `03}", } @MISC{Vadhan07, author = {Salil Vadhan}, title = {Lecture Notes on Pseudorandomness}, howpublished = {\url{http://eecs.harvard.edu/~salil/cs225}}, year = {2007}, month = {Spring}, OPTnote = {}, OPTabstract = {}, OPTkeywords = {}, OPTsource = {}, } @article{GoldreichRoSu00, author = {Oded Goldreich and Dana Ron and Madhu Sudan}, title = {Chinese remaindering with errors}, journal = {IEEE Transactions on Information Theory}, volume = 46, number = 4, pages = {1330-1338}, year = 2000} @INPROCEEDINGS{AllenderBuKoMeRo02, AUTHOR = "Eric Allender and Harry Buhrman and Michal Kouck{'y} and Dieter van Melkebeek and Detlef Ronneburger", TITLE = "Power from Random Strings", BOOKTITLE = "Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science", YEAR = "2002", pages = "669--678" } @INPROCEEDINGS{Trevisan03, AUTHOR = "Luca Trevisan", TITLE = "List Decoding Using the {XOR} Lemma", BOOKTITLE = "Proceedings of the 44th IEEE Symposium on Foundations of Computer Science", YEAR = "2003", pages = "126--135", address = "Cambridge, MA", month = "October" } @incollection {Barak02, AUTHOR = {Barak, Boaz}, TITLE = {A probabilistic-time hierarchy theorem for ``slightly non-uniform'' algorithms}, BOOKTITLE = {Randomization and approximation techniques in computer science}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {2483}, PAGES = {194--208}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2002}, MRCLASS = {68Q15}, MRNUMBER = {MR2047030 (2004m:68056)}, } @unpublished{MP05, title = {A Generic Time Hierarchy for Semantic Models With One Bit of Advice}, author = {D. van Melkebeek and K. Pervyshev}, note = {Manuscript}, year = 2005} @inproceedings{FS04, author = {Lance Fortnow and Rahul Santhanam}, title = {Hierarchy theorems for probabilistic polynomial time}, booktitle = focs04, pages = {316-324}, year = 2004} @inproceedings{FST05, author = {Lance Fortnow and Rahul Santhanam and Luca Trevisan}, title = {Hierarchies for semantic classes}, booktitle = stoc05, pages = {348-355}, year = 2005} @techreport{GST04, number = {TR04-093}, author= {Oded Goldreich and Madhu Sudan and Luca Trevisan}, institution = {ECCC}, title = {From logarithmic advice to single-bit advice}, year = 2004} @article {MiltersenVi05, AUTHOR = {Miltersen, Peter Bro and Vinodchandran, N. V.}, TITLE = {Derandomizing {A}rthur-{M}erlin games using hitting sets}, JOURNAL = {Computational Complexity}, VOLUME = {14}, YEAR = {2005}, NUMBER = {3}, PAGES = {256--279}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (03D15 68Q10 68Q17)}, MRNUMBER = {2183781 (2006k:68030)}, MRREVIEWER = {Lane A. Hemaspaandra}, DOI = {10.1007/s00037-005-0197-7}, URL = {http://dx.doi.org/10.1007/s00037-005-0197-7}, } @article {Shaltiel11-Yao, AUTHOR = {Shaltiel, Ronen}, TITLE = {Weak derandomization of weak algorithms: explicit versions of {Y}ao's lemma}, JOURNAL = {Computational Complexity}, VOLUME = {20}, YEAR = {2011}, NUMBER = {1}, PAGES = {87--143}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68W20)}, MRNUMBER = {2796059}, MRREVIEWER = {Andr{\'e} Nuno Carvalho Souto}, DOI = {10.1007/s00037-011-0006-4}, URL = {http://dx.doi.org/10.1007/s00037-011-0006-4}, } @article {Viola07, AUTHOR = {Viola, Emanuele}, TITLE = {Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2006/07}, NUMBER = {5}, PAGES = {1387--1403 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q15 (68Q10 68Q17)}, MRNUMBER = {2284087 (2008b:68036)}, DOI = {10.1137/050640941}, URL = {http://dx.doi.org/10.1137/050640941}, } @article {KinneMeSh12, AUTHOR = {Kinne, Jeff and van Melkebeek, Dieter and Shaltiel, Ronen}, TITLE = {Pseudorandom generators, typically-correct derandomization, and dircuit lower bounds}, JOURNAL = {Computational Complexity}, VOLUME = {21}, YEAR = {2012}, NUMBER = {1}, PAGES = {3--61}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q17 (68Q15 68Q25 68Q87 68W20)}, MRNUMBER = {2901240}, DOI = {10.1007/s00037-011-0019-z}, URL = {http://dx.doi.org/10.1007/s00037-011-0019-z}, } @INPROCEEDINGS{ReingoldTrVa04, author = {Omer Reingold and Luca Trevisan and Salil Vadhan}, title = {Notions of Reducibility between Cryptographic Primitives}, booktitle = {Proceedings of the First Theory of Cryptography Conference (TCC `04)}, OPTcrossref = {}, OPTkey = {}, pages = {1--20}, year = {2004}, editor = {M. Naor}, volume = {2951}, OPTnumber = {}, series = {Lecture Notes in Computer Science}, c-address = {Cambridge, MA}, month = {19--21 February}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, OPTannote = {} } @article {Viola04, AUTHOR = {Emanuele Viola}, TITLE = {The Complexity of Constructing Pseudorandom Generators from Hard Functions}, JOURNAL = {Computational Complexity}, VOLUME = {13}, YEAR = {2004}, NUMBER = {3-4}, PAGES = {147--188} } @INPROCEEDINGS{GuruswamiVa05, AUTHOR = "Venkatesan Guruswami and Salil Vadhan", TITLE = "A Lower Bound on List Size for List Decoding", BOOKTITLE = "Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM `05)", YEAR = "2005", editor = "Chandra Chekuri and Klaus Jansen and Jos{\'e} D. P. Rolim and Luca Trevisan", OPTvolume = "", number = "3624", series = "Lecture Notes in Computer Science", pages = "318--329", address = "Berkeley, CA", month = "August", OPTorganization = "", publisher = "Springer", OPTabstract = "", OPTkeywords = "", OPTfile = F } @article(Blinovsky86, author="Volodia M. Blinovsky", title="Bounds for codes in the case of list decoding of finite volume", journal="Problems of Information Transmission", volume=22, number=1, pages="7-19", year="1986") @INCollection{Shaltiel04, AUTHOR = "Ronen Shaltiel", editor = "G. Paun and G. Rozenberg and A. Salomaa", title = "Recent Developments in Extractors", PUBLISHER = "World Scientific", YEAR = "2004", booktitle = "Current Trends in Theoretical Computer Science", volume = "1: Algorithms and Complexity", pages = {189--228} } @INCollection{Kabanets04, AUTHOR = "Valentine Kabanets", editor = "G. Paun and G. Rozenberg and A. Salomaa", title = "Derandomization: A Brief Overview", PUBLISHER = "World Scientific", YEAR = "2004", booktitle = "Current Trends in Theoretical Computer Science", volume = "1: Algorithms and Complexity", pages = {165--188} } @TechReport{Goldreich05, author = {Oded Goldreich}, title = {On Promise Problems (in memory of {S}himon {E}ven, 1935--2004)}, institution = {Electronic Colloquium on Computational Complexity}, year = {2005}, OPTkey = {}, OPTtype = {}, number = {TR05-018}, OPTaddress = {}, note = {See June 2005 revision, available from author's homepage}, OPTannote = {} } @article {Lu01, AUTHOR = {Lu, Chi-Jen}, TITLE = {Derandomizing {A}rthur-{M}erlin games under uniform assumptions}, JOURNAL = {Computational Complexity}, VOLUME = {10}, YEAR = {2001}, NUMBER = {3}, PAGES = {247--259}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q10 (68Q15 68Q17)}, MRNUMBER = {MR1903838 (2003d:68072)}, MRREVIEWER = {Uwe Sch{\"o}ning}, } @article {BogdanovTr06, AUTHOR = {Bogdanov, Andrej and Trevisan, Luca}, TITLE = {Average-case complexity}, JOURNAL = {Foundations and Trends${}^\circledR$ in Theoretical Computer Science}, VOLUME = {2}, YEAR = {2006}, NUMBER = {1}, PAGES = {1--106}, ISSN = {1551-305X}, ISBN = {1-933019-49-2}, MRCLASS = {68Q15 (68Q17 68Q25)}, MRNUMBER = {2453146 (2010b:68048)}, DOI = {10.1561/0400000004}, URL = {http://dx.doi.org/10.1561/0400000004}, } @TECHREPORT{AngluinLi83, title={Provable Security of Cryptosystems: A Survey}, author = {Dana Angluin and David Lichtenstein}, institution = {Yale University, Department of Computer Science}, year = {1983}, number = {YALEU/DCS/TR-288} } @article {KabanetsIm04, AUTHOR = {Kabanets, Valentine and Impagliazzo, Russell}, TITLE = {Derandomizing polynomial identity tests means proving circuit lower bounds}, JOURNAL = {Computational Complexity}, VOLUME = {13}, YEAR = {2004}, NUMBER = {1-2}, PAGES = {1--46}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q17)}, MRNUMBER = {MR2105971 (2005i:68025)}, MRREVIEWER = {Johan H{\aa}stad}, } @article {ImpagliazzoKaWi02, AUTHOR = {Impagliazzo, Russell and Kabanets, Valentine and Wigderson, Avi}, TITLE = {In search of an easy witness: exponential time vs.\ probabilistic polynomial time}, OPTNOTE = {Special issue on complexity, 2001 (Chicago, IL)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {65}, YEAR = {2002}, NUMBER = {4}, PAGES = {672--694}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (94C10)}, MRNUMBER = {MR1964649 (2004h:68044)}, } @article {GutfreundShTa03, AUTHOR = {Gutfreund, Dan and Shaltiel, Ronen and {Ta-S}hma, Amnon}, TITLE = {Uniform hardness versus randomness tradeoffs for {A}rthur-{M}erlin games}, JOURNAL = {Computational Complexity}, VOLUME = {12}, YEAR = {2003}, NUMBER = {3-4}, PAGES = {85--130}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15}, MRNUMBER = {MR2090019 (2005h:68038)}, MRREVIEWER = {Peter Bro Miltersen}, } @article {Umans03, AUTHOR = {Umans, Christopher}, TITLE = {Pseudo-random generators for all hardnesses}, OPTNOTE = {Special issue on STOC2002 (Montreal, QC)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {67}, YEAR = {2003}, NUMBER = {2}, PAGES = {419--440}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (11K45 65C10)}, MRNUMBER = {MR2022839 (2004k:68055)}, MRREVIEWER = {Peter Bro Miltersen}, } @article {RadhakrishnanTa00, AUTHOR = {Radhakrishnan, Jaikumar and {Ta-S}hma, Amnon}, TITLE = {Bounds for dispersers, extractors, and depth-two superconcentrators}, JOURNAL = {SIAM Journal on Discrete Mathematics}, VOLUME = {13}, YEAR = {2000}, NUMBER = {1}, PAGES = {2--24 (electronic)}, ISSN = {0895-4801}, MRCLASS = {94C15 (05C35)}, MRNUMBER = {MR1737930 (2001a:94055)}, MRREVIEWER = {W.-K. Chen}, } @article {Vinodchandran04, AUTHOR = {Vinodchandran, N. V.}, TITLE = {{${\rm AM\sb {exp}}\not\subseteq({\rm NP}\cap{\rm coNP})/{\rm poly}$}}, JOURNAL = {Information Processing Letters}, VOLUME = {89}, YEAR = {2004}, NUMBER = {1}, PAGES = {43--47}, ISSN = {0020-0190}, CODEN = {IFPLAT}, MRCLASS = {68Q15 (03D15 68Q10)}, MRNUMBER = {MR2025889 (2005e:68072)}, MRREVIEWER = {Lane Hemaspaandra}, } @incollection {CaiNeSi99, AUTHOR = {Cai, Jin-Yi and Nerurkar, Ajay and Sivakumar, D.}, TITLE = {Hardness and hierarchy theorems for probabilistic quasi-polynomial time}, BOOKTITLE = {Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999)}, PAGES = {726--735 (electronic)}, PUBLISHER = {ACM}, ADDRESS = {New York}, YEAR = {1999}, MRCLASS = {68Q15}, MRNUMBER = {2001i:68048}, } @article{BK95, title = {Designing programs that check their work}, author = {Manuel Blum and Sampath Kannan}, journal = {Journal of the {ACM}}, volume = 42, number = 1, pages = {269--291}, year = 1995} @inproceedings {ImpagliazzoLe90, title = {No Better Ways to Generate Hard {NP} Instances than Picking Uniformly at Random}, author = {R. Impagliazzo and L. Levin}, booktitle = {Proceedings of the 31st IEE Simposium on Foundations of Computer Science}, pages = {812--821}, year = 1990} @article {BenDavidChGoLu92, author = {S. {Ben-D}avid and B. Chor and O. Goldreich and M. Luby}, title = {On the theory of average-case complexity}, journal = {J. of Computer and System Sciences}, volume =44, number = 2, year = 1992, pages = {193--219}} @Article{Levin86, title={Average Case Complete Problems}, author={Leonid A. Levin}, pages={285--286}, journal=sicomp, year=1986, month=feb, volume=15, number=1, source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib} } @TechReport{GoldreichNiWi10, author = {Oded Goldreich and Noam Nisan and Avi Wigderson}, title = {On {Y}ao's {XOR} lemma}, institution = {Electronic Colloquium on Computational Complexity}, year = {2010}, OPTkey = {}, OPTtype = {}, number = {TR95--050, revision 2}, OPTaddress = {}, month = {June}, note = webstart # {http://} # webmid # {www.eccc.uni-trier.de/} # webmid # {eccc} # webend, OPTannote = {} } @TechReport{Vadhan98-eccc, author = {Salil P. Vadhan}, title = {Extracting all the Randomness from a Weakly Random Source}, institution = {Electronic Colloquium on Computational Complexity}, year = {1998}, OPTkey = {}, OPTtype = {}, number = {TR98--047}, OPTaddress = {}, OPTmonth = {}, note = webstart # {http://} # webmid # {www.eccc.uni-trier.de/} # webmid # {eccc} # webend, OPTannote = {} } @Article{FeigenbaumFo93, title={Random-Self-Reducibility of Complete Sets}, author={Joan Feigenbaum and Lance Fortnow}, pages={994--1005}, journal=sicomp, year=1993, month=oct, volume=22, number=5, source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib} } @string{cc = {Computational Complexity}} @Article{FeigeLu96, title={On the Hardness of Computing the Permanent of Random Matrices}, author={Uriel Feige and Carsten Lund}, journal=cc, pages={101--132}, year=1996, volume=6, number=2, source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/cc/cc.bib} } @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 {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 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}, } @article{ArLiRuSu99, title={Reconstructing Algebraic Functions from Mixed Data}, author={Ar, Sigal and Lipton, Richard J. and Rubinfeld, Ronitt and Sudan, Madhu}, journal = sicomp, year = 1999, volume = 28, pages = {487--510}, note = {}, number = 2} @inproceedings{ AK97, author = {V. Arvind and J. K{\"o}bler}, title = {On resource-bounded measure and pseudorandomness}, booktitle = {Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science}, publisher = {LNCS 1346, Springer-Verlag}, pages = {235-249}, year = 1997} @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} } @Proceedings{STOC31, title={Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing}, booktitle={Proceedings of the Thirty-First Annual ACM Symposium on the Theory of Computing}, month={1--4 } # may, year=1999, address={Atlanta, Georgia}, 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" } @InProceedings{Sipser83, title={A Complexity Theoretic Approach to Randomness}, author={Sipser, Michael}, pages={330--335}, crossref={STOC15}, source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib} } @Proceedings{STOC15, title={15th Annual ACM Symposium on Theory of Computing}, booktitle={15th Annual ACM Symposium on Theory of Computing}, month={25--27 } # apr, year=1983, address={Boston, Massachusetts}, c-organization={ACM}, key={ACM}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.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 = webstart # {http://} # webmid # {www.eccc.uni-trier.de/} # webmid # {eccc} # webend, 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} } @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={19th Annual ACM Symposium on Theory of Computing}, booktitle={19th 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} } @inproceedings{ChorGoHaFrRuSm85, author = {Benny Chor and Oded Goldreich and Johan H{\aa}stad and Joel Friedman and Steven Rudich and Roman Smolensky}, title = {The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)}, booktitle = {FOCS}, year = {1985}, pages = {396-407}, crossref = {DBLP:conf/focs/FOCS26}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/focs/FOCS26, title = {26th Annual Symposium on Foundations of Computer Science, 21-23 October 1985, Portland, Oregon, USA}, booktitle = {FOCS}, publisher = {IEEE}, year = {1985}, bibsource = {DBLP, http://dblp.uni-trier.de} } @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} } @article {vonNeumann51, author = {J. von Neumann}, title = {Various techniques used in connection with random digits}, journal = {National Bureau of Standards, Applied Mathematics Series}, volume = 12, pages = {36--38}, year = 1951} @PhdThesis{Vazirani86, author = {Umesh V. Vazirani}, title = {Randomness, Adversaries, and Computation}, school = {University of California, Berkeley}, year = {1984}, OPTkey = {}, OPTtype = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @Misc{GoldreichWi94, OPTkey = {}, author = {Oded Goldreich and Avi Wigderson}, title = {Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing}, howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR94-002}, OPTmonth = {}, year = {1994}, note = {Revised December 1996.} # webstart # {http://} # webmid # {www.eccc.uni-trier.de/} # webmid # {eccc} # webend, 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} } @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-S}hma}}, 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}, month = {February}, 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 = {Franco P. Preparata and 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 {AlonSp00, AUTHOR = {Alon, Noga and Spencer, Joel H.}, TITLE = {The probabilistic method}, SERIES = {Wiley-Interscience Series in Discrete Mathematics and Optimization}, EDITION = {Second}, NOTE = {With an appendix on the life and work of Paul Erd\H os}, PUBLISHER = {Wiley-Interscience [John Wiley \& Sons]}, ADDRESS = {New York}, YEAR = {2000}, PAGES = {xviii+301}, ISBN = {0-471-37046-0}, MRCLASS = {60-02 (05C80 60C05 60F99 60G42)}, MRNUMBER = {MR1885388 (2003f:60003)}, MRREVIEWER = {Bert Fristedt}, } @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 } # webstart # {http://} # webmid # {www.wisdom.weizmann.ac.il/} # webmid # til # {oded} # webend, OPTannote = {} } @book{Goldreich99, AUTHOR = {Goldreich, Oded}, TITLE = {Modern cryptography, probabilistic proofs and pseudorandomness}, SERIES = {Algorithms and Combinatorics}, VOLUME = {17}, PUBLISHER = {Springer-Verlag}, ADDRESS = {Berlin}, YEAR = {1999}, PAGES = {xvi+182}, ISBN = {3-540-64766-X}, MRCLASS = {94A60 (68-02 68P25 68Q15)}, MRNUMBER = {MR1665938 (2000f:94029)}, MRREVIEWER = {Simon R. Blackburn}, } @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 = "" } @InProceedings{Impagliazzo95, title={Hard-core distributions for somewhat hard problems}, author={Russell Impagliazzo}, pages={538--545}, crossref={FOCS36}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @Proceedings{FOCS36, title={36th Annual Symposium on Foundations of Computer Science}, booktitle={36th Annual Symposium on Foundations of Computer Science}, month={23--25 } # oct, year=1995, address={Milwaukee, Wisconsin}, organization={IEEE}, crossrefonly=1, pubinfo={IEEE Computer Society Press Order Number PR07183; Library of Congress Number 80-646634; IEEE Catalog Number 95CH35834; ISBN 0-8186-7183-1 (paper); ISBN 0-8186-7184-X (microfiche); ISSN 0272-5428}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @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} } @inproceedings{ACR97, author = {Andreev, Alexander and Clementi, Andrea and Rolim, Jos{\'e}}, title = {Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs}, booktitle = {Proceedings of ICALP'97}, year = 1997, pages = {177-187}, publisher = {LNC 1256S, Springer-Verlag}} @article {BFMT00, title = {Using autoreducibility to separate complexity classes}, author = {H. Buhrman and L. Fortnow and D. {van M}elkebeek and L. Torenvliet}, journal = sicomp, volume = 29, year = 2000, pages = {1497--1520}} @Article{BabaiFoNiWi93, title={{BPP} Has Subexponential Time Simulations Unless {EXPTIME} has Publishable Proofs}, author={L{\'a}szl{\'o} Babai and Lance Fortnow and Noam Nisan and Avi Wigderson}, journal=cc, pages={307--318}, year=1993, volume=3, number=4, source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/cc/cc.bib} } @incollection {Renyi61, AUTHOR = {R{\'e}nyi, Alfr{\'e}d}, TITLE = {On measures of entropy and information}, BOOKTITLE = {Proc. 4th {B}erkeley {S}ympos. {M}ath. {S}tatist. and {P}rob., {V}ol. {I}}, PAGES = {547--561}, PUBLISHER = {Univ. California Press}, ADDRESS = {Berkeley, Calif.}, YEAR = {1961}, MRCLASS = {94.20}, MRNUMBER = {0132570 (24 \#A2410)}, MRREVIEWER = {S. Kullback}, } @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 = "" } @article {ArvindKo01, AUTHOR = {Arvind, V. and K{\"o}bler, Johannes}, TITLE = {On pseudorandomness and resource-bounded measure}, JOURNAL = {Theoretical Computer Science}, VOLUME = {255}, YEAR = {2001}, NUMBER = {1-2}, PAGES = {205--221}, ISSN = {0304-3975}, CODEN = {TCSDI}, MRCLASS = {68Q15}, MRNUMBER = {1819074 (2002c:68030)}, MRREVIEWER = {J{\"o}rg Rothe}, DOI = {10.1016/S0304-3975(99)00164-4}, URL = {http://dx.doi.org/10.1016/S0304-3975(99)00164-4}, } @article {KlivansMe02, AUTHOR = {Klivans, Adam R. and van Melkebeek, Dieter}, TITLE = {Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {31}, YEAR = {2002}, NUMBER = {5}, PAGES = {1501--1526 (electronic)}, ISSN = {0097-5397}, MRCLASS = {68Q15 (68Q25 68R10)}, MRNUMBER = {1936656 (2003i:68038)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1137/S0097539700389652}, URL = {http://dx.doi.org/10.1137/S0097539700389652}, } @article {ImpagliazzoWi01, AUTHOR = {Impagliazzo, Russell and Wigderson, Avi}, TITLE = {Randomness vs time: derandomization under a uniform assumption}, NOTE = {Special issue on FOCS 98 (Palo Alto, CA)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {63}, YEAR = {2001}, NUMBER = {4}, PAGES = {672--688}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15 (68Q10)}, MRNUMBER = {1894528 (2003e:68039)}, MRREVIEWER = {Johan H{\aa}stad}, DOI = {10.1006/jcss.2001.1780}, URL = {http://dx.doi.org/10.1006/jcss.2001.1780}, } @InProceedings{GoldreichLe89, title={A Hard-Core Predicate for all One-Way Functions}, author={Goldreich, Oded and Levin, Leonid A.}, pages={25--32}, 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{BabaiFoLeSz91, author = {L{\'a}szl{\'o} Babai and Lance Fortnow and Leonid A. Levin and Mario Szegedy}, title = {Checking Computations in Polylogarithmic Time}, booktitle = {STOC}, year = {1991}, pages = {21-31}, ee = {http://doi.acm.org/10.1145/103418.103428}, crossref = {DBLP:conf/stoc/STOC23}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stoc/STOC23, editor = {Cris Koutsougeras and Jeffrey Scott Vitter}, title = {Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA}, booktitle = {STOC}, publisher = {ACM}, year = {1991}, isbn = {0-89791-397-3}, bibsource = {DBLP, http://dblp.uni-trier.de} } @string{jcomp = {Journal of Complexity}} @Article{Sudan97, title={Decoding of {Reed} {Solomon} Codes beyond the Error-Correction Bound}, author={Madhu Sudan}, pages={180--193}, journal=jcomp, year=1997, month=mar, volume=13, number=1, source={http://theory.lcs.mit.edu/~dmjones/hbp/jcomp/jcomp.bib} } @InProceedings{ArLiRuSu92, title={Reconstructing Algebraic Functions from Mixed Data}, author={Ar, Sigal and Lipton, Richard J. and Rubinfeld, Ronitt and Sudan, Madhu}, pages={503--512}, crossref={FOCS33}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @Unpublished{Goldreich97-xor, author = {Oded Goldreich}, title = {Three {XOR} Lemmas --- An Exposition}, note = {Available from } # webstart # {http://} # webmid # {www.wisdom.weizmann.ac.il/} # webmid # til # {oded/} # webend, OPTkey = {}, year = {1997}, month = {November}, OPTannote = {} } @InProceedings{AroraSu97, title={Improved Low Degree Testing and its Applications}, author={Sanjeev Arora and Madhu Sudan}, pages={485--495}, crossref={STOC29}, source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib} } @Unpublished{Goldreich97-samp, author = {Oded Goldreich}, title = {A Computational Perspective on Sampling (survey)}, note = {Available from } # webstart # {http://} # webmid # {www.wisdom.weizmann.ac.il/} # webmid # til # {oded/} # webend, OPTkey = {}, year = {1997}, month = {May}, OPTannote = {} } @InProceedings{Friedman92, title={On the Bit Extraction Problem}, author={Friedman, Joel}, pages={314--319}, crossref={FOCS33}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @Proceedings{FOCS33, title={33rd Annual Symposium on Foundations of Computer Science}, booktitle={33rd Annual Symposium on Foundations of Computer Science}, month={24--27 } # oct, year=1992, address={Pittsburgh, Pennsylvania}, organization={IEEE}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @InProceedings{Vazirani85, title={Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract)}, author={Vazirani, Umesh V.}, pages={366--378}, crossref={STOC17}, source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib} } @Proceedings{STOC17, title={Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing}, booktitle={Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing}, month={6--8 } # may, year=1985, address={Providence, Rhode Island}, c-organization={ACM}, key={ACM}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib} } @string{lncs={Lecture Notes in Computer Science}} @Proceedings{CRYPTO85, title={Advances in Cryptology---CRYPTO~'85}, booktitle={Advances in Cryptology---CRYPTO~'85}, editor={Hugh C. Williams}, series=lncs, volume=218, year=1985, month={18--22~} # aug, c-address={University of California, Santa Barbara}, publisher={Springer-Verlag, 1986}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/hbp/crypto/crypto.bib} } @UNPUBLISHED{GuruswamiSu01, AUTHOR = {Venkatesan Guruswami and Madhu Sudan}, TITLE = {Extensions to the Johnson Bound}, NOTE = {Unpublished Manuscript}, year = {2001}, month = {February} } @TechReport{GoldreichRuSu98, author = {Oded Goldreich and Ronitt Rubinfeld and Madhu Sudan}, title = {Learning Polynomials with Queries --- the Highly Noisy Case}, institution = {Electronic Colloquium on Computational Complexity}, year = {1998}, OPTkey = {}, OPTtype = {}, number = {TR98-060}, OPTaddress = {}, OPTmonth = {}, note = {Preliminary version in FOCS `95}, OPTannote = {} } @InProceedings{CaiPaSi99, author = {Jin-Yi Cai and A. Pavan and D. Sivakumar}, title = {On the Hardness of the Permanent}, booktitle = {16th International Symposium on Theoretical Aspects of Computer Science}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1999}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, series = {Lecture Notes in Computer Science}, address = {Trier, Germany}, month = {March 4--6}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, OPTannote = {} } @Misc{Wigderson98, OPTkey = {}, author = {Avi Wigderson}, title = {Personal communication}, OPThowpublished = {}, month = {October}, year = {1998}, OPTnote = {}, OPTannote = {} } @Misc{KumarSi98, OPTkey = {}, author = {{S. Ravi} Kumar and D. Sivakumar}, title = {Personal communication}, OPThowpublished = {}, month = {October}, year = {1998}, OPTnote = {}, OPTannote = {} } @Article{GoldreichGoMi86, title={How to Construct Random Functions}, author={Oded Goldreich and Shafi Goldwasser and Silvio Micali}, area={Theory of Computation}, pages={792--807}, journal=jacm, month=oct, year=1986, volume=33, number=4, keywords={}, cr-categories={}, source={http://theory.lcs.mit.edu/~jacm/jacm.bib} } @Article{Valiant84, author = {Leslie G. Valiant}, title = {A Theory of the Learnable}, journal = {Communications of the ACM}, year = {1984}, OPTkey = {}, volume = {27}, number = {11}, pages = {1134--1142}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @string{tcs = {Theoretical Computer Science}} @Article{JerrumVaVa86, title={Random Generation of Combinatorial Structures from a Uniform Distribution}, author={Marc R. Jerrum and Leslie G. Valiant and Vijay V. Vazirani}, pages={169--188}, journal=tcs, year=1986, volume=43, number={2--3}, source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib} } @Article{Stockmeyer85, title={On Approximation Algorithms for {{\#P}}}, author={Larry Stockmeyer}, pages={849--861}, journal=sicomp, month=nov, year=1985, volume=14, number=4, preliminary={STOC::Stockmeyer1983:118}, source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib} } @Book{Papadimitriou94, author = {Christos H. Papadimitriou}, ALTeditor = {}, title = {Computational Complexity}, publisher = {Addison--Wesley}, year = {1994}, OPTkey = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @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} } @incollection {Rabin76}, AUTHOR = {Rabin, Michael O.}, TITLE = {Probabilistic algorithms}, BOOKTITLE = {Algorithms and complexity ({P}roc. {S}ympos., {C}arnegie-{M}ellon {U}niv., {P}ittsburgh, {P}a., 1976)}, PAGES = {21--39}, PUBLISHER = {Academic Press}, ADDRESS = {New York}, YEAR = {1976}, MRCLASS = {68A10 (10-04)}, MRNUMBER = {MR0464678 (57 \#4603)}, MRREVIEWER = {Forbes D. Lewis}, } @article {Rabin80, AUTHOR = {Rabin, Michael O.}, TITLE = {Probabilistic algorithm for testing primality}, JOURNAL = {Journal of Number Theory}, VOLUME = {12}, YEAR = {1980}, NUMBER = {1}, PAGES = {128--138}, ISSN = {0022-314X}, CODEN = {JNUTA9}, MRCLASS = {10-04 (10A25)}, MRNUMBER = {81f:10003}, MRREVR = {D. H. Lehmer}, } @article {SolovaySt77, AUTHOR = {Solovay, R. and Strassen, V.}, TITLE = {A fast {M}onte-{C}arlo test for primality}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {6}, YEAR = {1977}, NUMBER = {1}, PAGES = {84--85}, MRCLASS = {10A25 (10-04)}, MRNUMBER = {55 #2732}, MRREVR = {George Marsaglia}, } @article {KarpLuMa89, AUTHOR = {Karp, Richard M. and Luby, Michael and Madras, Neal}, TITLE = {Monte {C}arlo approximation algorithms for enumeration problems}, JOURNAL = {Journal of Algorithms}, VOLUME = {10}, YEAR = {1989}, NUMBER = {3}, PAGES = {429--448}, ISSN = {0196-6774}, CODEN = {JOALDV}, MRCLASS = {05A15 (03B05 03B35 03D15 68Q25)}, MRNUMBER = {90j:05015}, MRREVR = {D. M. Topkis}, } @Article{Miller76, title={Riemann's Hypothesis and Tests for Primality}, author={Gary L. Miller}, pages={300--317}, journal=jcss, year=1976, month=dec, volume=13, number=3, preliminary={STOC::Miller1975}, source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib} } @article {JerrumSi89, AUTHOR = {Jerrum, Mark and Sinclair, Alistair}, TITLE = {Approximating the permanent}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {18}, YEAR = {1989}, NUMBER = {6}, PAGES = {1149--1178}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {05C70 (15A15 60J20 68Q20)}, MRNUMBER = {91a:05075}, MRREVR = {David J. Aldous}, } @article {FischerLyPa85, AUTHOR = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael S.}, TITLE = {Impossibility of distributed consensus with one faulty process}, JOURNAL = {J. Assoc. Comput. Mach.}, FJOURNAL = {Journal of the ACM}, VOLUME = {32}, YEAR = {1985}, NUMBER = {2}, PAGES = {374--382}, ISSN = {0004-5411}, CODEN = {JACOAH}, MRCLASS = {68M10 (68Q10)}, MRNUMBER = {87e:68002}, } @incollection {Ben-OrLiSa88, AUTHOR = {{Ben-O}r, M. and Linial, N. and Saks, M.}, TITLE = {Collective coin flipping and other models of imperfect randomness}, BOOKTITLE = {Combinatorics (Eger, 1987)}, PAGES = {75--112}, PUBLISHER = {North-Holland}, ADDRESS = {Amsterdam}, YEAR = {1988}, MRCLASS = {68Q05 (90D40)}, MRNUMBER = {94f:68076}, MRREVR = {Mark R. Jerrum}, } @InProceedings{Ben-OrLi85, title={Collective Coin Flipping, Robust Voting Schemes and Minima of {Banzhaf} Values}, author={{Ben-O}r, Michael and Linial, Nathan}, pages={408--416}, 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 {LinialLiSa89, AUTHOR = {Lichtenstein, D. and Linial, N. and Saks, M.}, TITLE = {Some extremal problems arising from discrete control processes}, JOURNAL = {Combinatorica}, FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing}, VOLUME = {9}, YEAR = {1989}, NUMBER = {3}, PAGES = {269--287}, ISSN = {0209-9683}, CODEN = {COMBDI}, MRCLASS = {68R10}, MRNUMBER = {91k:68163}, } @inproceedings{ImpagliazzoZu89, author = {Russell Impagliazzo and David Zuckerman}, title = {How to Recycle Random Bits}, booktitle = {30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, North Carolina)}, year = {1989}, pages = {248-253}, publisher = {IEEE}, bibsource = {DBLP, http://dblp.uni-trier.de} } @InProceedings{CohenWi89, title={Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract)}, author={Cohen, Aviad and Wigderson, Avi}, pages={14--19}, booktitle = {30th Annual Symposium on Foundations of Computer Science (Research Triangle Park, North Carolina)}, publisher = {IEEE}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}, year={1989} } @InProceedings{KahnKaLi88, title={The Influence of Variables on {Boolean} Functions (Extended Abstract)}, author={Kahn, Jeff and Kalai, Gil and Linial, Nathan}, pages={68--80}, crossref={FOCS29}, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @Proceedings{FOCS29, title={29th Annual Symposium on Foundations of Computer Science}, booktitle={29th Annual Symposium on Foundations of Computer Science}, month={24--26 } # oct, year=1988, address={White Plains, New York}, organization={IEEE}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib} } @Unpublished{Dodis00, author = {Yevgeniy Dodis}, title = {Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping}, note = {Unpublished manuscript}, OPTkey = {}, month = {April}, year = {2000}, OPTannote = {} } @ARTICLE{PlackettBu45, AUTHOR = {Plackett, R. L. and Burman, J. E.}, TITLE = {The design of optimum multi-factorial experiments}, JOURNAL = {Biometrika}, YEAR = {1945}, volume = {33}, pages = {305--325} } @article {Stinson94b, AUTHOR = {Stinson, D. R.}, TITLE = {Combinatorial techniques for universal hashing}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {48}, YEAR = {1994}, NUMBER = {2}, PAGES = {337--346}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68P20 (68P10 68R05)}, MRNUMBER = {1275037 (95d:68033)}, DOI = {10.1016/S0022-0000(05)80007-8}, URL = {http://dx.doi.org/10.1016/S0022-0000(05)80007-8}, } @article {Stinson92, AUTHOR = {Stinson, D. R.}, TITLE = {Combinatorial characterizations of authentication codes}, JOURNAL = {Designs, Codes and Cryptography. An International Journal}, VOLUME = {2}, YEAR = {1992}, NUMBER = {2}, PAGES = {175--187}, ISSN = {0925-1022}, CODEN = {DCCREC}, MRCLASS = {94A60 (68P25 94B25)}, MRNUMBER = {1171533 (93d:94014)}, MRREVIEWER = {Antoine Lobstein}, DOI = {10.1007/BF00124896}, URL = {http://dx.doi.org/10.1007/BF00124896}, } @incollection {BierbrauerJoKaSm93, AUTHOR = {Bierbrauer, J{\"u}rgen and Johansson, Thomas and Kabatianskii, Gregory and Smeets, Ben}, TITLE = {On families of hash functions via geometric codes and concatenation}, BOOKTITLE = {Advances in cryptology---{CRYPTO} '93 ({S}anta {B}arbara, {CA}, 1993)}, SERIES = {Lecture Notes in Comput. Sci.}, VOLUME = {773}, PAGES = {331--342}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1994}, MRCLASS = {94A60 (68P20 94B27)}, MRNUMBER = {1288973 (95e:94024)}, DOI = {10.1007/3-540-48329-2_28}, URL = {http://dx.doi.org/10.1007/3-540-48329-2_28}, } @article {Stinson94, AUTHOR = {Stinson, D. R.}, TITLE = {Universal hashing and authentication codes}, JOURNAL = {Designs, Codes and Cryptography}, VOLUME = {4}, YEAR = {1994}, NUMBER = {4}, PAGES = {369--380}, ISSN = {0925-1022}, CODEN = {DCCREC}, MRCLASS = {94A60 (68P20)}, MRNUMBER = {1290620 (95g:94018)}, DOI = {10.1007/BF01388651}, URL = {http://dx.doi.org/10.1007/BF01388651}, } @article {KampZu06, AUTHOR = {Kamp, Jesse and Zuckerman, David}, TITLE = {Deterministic extractors for bit-fixing sources and exposure-resilient cryptography}, JOURNAL = {SIAM J. Comput.}, FJOURNAL = {SIAM Journal on Computing}, VOLUME = {36}, YEAR = {2006/07}, NUMBER = {5}, PAGES = {1231--1247}, ISSN = {0097-5397}, MRCLASS = {68Q10 (68W20 94A60)}, MRNUMBER = {2284079 (2007m:68061)}, MRREVIEWER = {Giovanni Di Crescenzo}, DOI = {10.1137/S0097539705446846}, URL = {http://dx.doi.org/10.1137/S0097539705446846}, } @InProceedings{CanettiDoHaKuSa00, title={Exposure-Resilient Functions and All-Or-Nothing Transforms}, author={Ran Canetti and Yevgeniy Dodis and Shai Halevi and Eyal Kushilevitz and Amit Sahai}, OPTpages={}, crossref={EUROCRYPT00}, source={http://theory.lcs.mit.edu/~dmjones/hbp/eurocrypt/eurocrypt.bib} } @Proceedings{EUROCRYPT00, title={Advances in Cryptology---EUROCRYPT~00}, booktitle={Advances in Cryptology---EUROCRYPT~00}, editor = {Bart Preneel}, year=2000, month={14--18~} # may, c-address={Bruges, Belgium}, series=lncs, OPTvolume={}, publisher={Springer-Verlag}, crossrefonly=1, source={http://theory.lcs.mit.edu/~dmjones/hbp/eurocrypt/eurocrypt.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}, 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}, } @article {LinialLuSaZu97, AUTHOR = {Linial, Nathan and Luby, Michael and Saks, Michael and Zuckerman, David}, TITLE = {Efficient construction of a small hitting set for combinatorial rectangles in high dimension}, JOURNAL = {Combinatorica}, VOLUME = {17}, YEAR = {1997}, NUMBER = {2}, PAGES = {215--234}, ISSN = {0209-9683}, MRCLASS = {68Q25 (68Q15)}, MRNUMBER = {1479299 (99d:68115)}, MRREVIEWER = {E. Rodney Canfield}, DOI = {10.1007/BF01200907}, URL = {http://dx.doi.org/10.1007/BF01200907}, } @InCollection{Ben-OrLi90, author = {Michael {Ben-O}r and Nathan Linial}, title = {Collective Coin-Flipping}, booktitle = {Randomness and Computation}, OPTcrossref = {}, OPTkey = {}, pages = {91--115}, publisher = {Academic Press}, year = {1990}, editor = {Silvio Micali}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTtype = {}, OPTchapter = {}, address = {New York}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @InProceedings{Saks96, title={Randomization and Derandomization in Space-Bounded Computation}, author={Michael Saks}, pages={128--149}, 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} } @Unpublished{DodisSaSm00, author = {Yevgeniy Dodis and Amit Sahai and Adam Smith}, title = {Optimal Lower Bound for Perfect All-or-Nothing Transforms}, note = {In preparation}, OPTkey = {}, month = {April}, year = {2000}, OPTannote = {} } @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 {AndreevClRoTr99, AUTHOR = {Andreev, Alexander E. and Clementi, Andrea E. F. and Rolim, Jos{\'e} D. P. and Trevisan, Luca}, TITLE = {Weak random sources, hitting sets, and {B}{P}{P} simulations}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {28}, YEAR = {1999}, NUMBER = {6}, PAGES = {2103--2116 (electronic)}, ISSN = {1095-7111}, MRCLASS = {68Q15 (65C99 68Q17 94A17)}, MRNUMBER = {2000h:68076}, MRREVIEWER = {Hsien-Kuei Hwang}, } @article {Valiant79, AUTHOR = {Valiant, L. G.}, TITLE = {The complexity of computing the permanent}, JOURNAL = {Theoretical Computer Science}, VOLUME = {8}, YEAR = {1979}, NUMBER = {2}, PAGES = {189--201}, ISSN = {0304-3975}, CODEN = {TCSDI}, MRCLASS = {68C25 (15A15)}, MRNUMBER = {80f:68054}, } @article {Toda91, AUTHOR = {Toda, Seinosuke}, TITLE = {P{P} is as hard as the polynomial-time hierarchy}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {20}, YEAR = {1991}, NUMBER = {5}, PAGES = {865--877}, ISSN = {0097-5397}, CODEN = {SMJCAT}, MRCLASS = {68Q15}, MRNUMBER = {93a:68047}, MRREVIEWER = {Lane Hemaspaandra}, } @inproceedings{I95:average, author = {Russell Impagliazzo}, title = {A Personal View of Average-Case Complexity}, booktitle = structures95, year = 1995, pages = {134-147}} @INPROCEEDINGS{Fortnow01, AUTHOR = "Lance Fortnow", TITLE = "Comparing Notions of Full Derandomization", crossref = {CCC01}, pages = "28--34" } @Proceedings{CCC01, title = {Proceedings of the Sixteenth Annual Conference on Computational Complexity}, booktitle = {Proceedings of the Sixteenth Annual Conference on Computational Complexity}, year = {2001}, OPTkey = {}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, c-address = {Chicago, Illinois}, month = {June 18--21}, organization = {IEEE}, OPTpublisher = {}, OPTnote = {}, OPTannote = {}, crossrefonly = 1 } @incollection {Trevisan06, AUTHOR = {Trevisan, Luca}, TITLE = {Pseudorandomness and combinatorial constructions}, BOOKTITLE = {International Congress of Mathematicians. Vol. III}, PAGES = {1111--1136}, PUBLISHER = {Eur. Math. Soc., Z\"urich}, YEAR = {2006}, MRCLASS = {68Q10 (05D40 68W20)}, MRNUMBER = {MR2275721}, } @article{Trevisan09, author = {Luca Trevisan}, title = {Guest column: additive combinatorics and theoretical computer science}, journal = {SIGACT News}, volume = {40}, number = {2}, year = {2009}, pages = {50-66}, ee = {http://doi.acm.org/10.1145/1556154.1556170}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article {ClementiRoTr98, AUTHOR = {Clementi, Andrea E. F. and Rolim, Jos{\'e} D. P. and Trevisan, Luca}, TITLE = {Recent advances towards proving {P}={BPP}}, JOURNAL = {Bulletin of the European Association for Theoretical Computer Science. EATCS}, VOLUME= {64}, YEAR = {1998}, PAGES = {96--103}, ISSN = {0252-9742}, MRCLASS = {68Q15 (03D15)}, MRNUMBER = {MR1618317 (99b:68081)}, } @article {LuTsWu08, AUTHOR = {Lu, Chi-Jen and Tsai, Shi-Chun and Wu, Hsin-Lung}, TITLE = {On the complexity of hardness amplification}, JOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory}, VOLUME = {54}, YEAR = {2008}, NUMBER = {10}, PAGES = {4575--4586}, ISSN = {0018-9448}, CODEN = {IETTAW}, MRCLASS = {68Q15}, MRNUMBER = {2589168 (2011g:68090)}, MRREVIEWER = {Johan H{\aa}stad}, DOI = {10.1109/TIT.2008.928988}, URL = {http://dx.doi.org/10.1109/TIT.2008.928988}, } @article {Trevisan01, AUTHOR = {Trevisan, Luca}, TITLE = {Extractors and pseudorandom generators}, JOURNAL = {Journal of the ACM}, VOLUME = {48}, YEAR = {2001}, NUMBER = {4}, PAGES = {860--879 (electronic)}, ISSN = {0004-5411}, MRCLASS = {68P30 (65C10 68W20)}, MRNUMBER = {MR2144932 (2005m:68064)}, } @Article{SudanTrVa01, author = {Madhu Sudan and Luca Trevisan and Salil Vadhan}, title = {Pseudorandom Generators without the {XOR} Lemma}, journal = {Journal of Computer and System Sciences}, year = {2001}, OPTkey = {}, volume = {62}, OPTnumber = {}, pages = {236--266}, OPTmonth = {}, note = {}, OPTannote = {} } @InProceedings{ImpagliazzoShWi00, author = {Russell Impagliazzo and Ronen Shaltiel and Avi Wigderson}, title = {Extractors and Pseudo-Random Generators with Optimal Seed Length}, OPTbooktitle = {}, crossref = {STOC32}, OPTkey = {}, pages = {1--10}, OPTyear = {}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, address = {Portland, Oregon}, month = {May}, c-organization = {ACM}, OPTpublisher = {}, note = {See also ECCC TR00-009}, OPTannote = {} } @Proceedings{STOC32, title={Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing}, booktitle={Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing}, month={21--23 } # may, year=2000, c-address={Portland, Oregon}, c-organization={ACM}, key={ACM}, crossrefonly=1 } @article {ShaltielUm06, AUTHOR = {Shaltiel, Ronen and Umans, Christopher}, TITLE = {Pseudorandomness for approximate counting and sampling}, JOURNAL = {Computational Complexity}, VOLUME = {15}, YEAR = {2006}, NUMBER = {4}, PAGES = {298--341}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15}, MRNUMBER = {2324420 (2008e:68045)}, DOI = {10.1007/s00037-007-0218-9}, URL = {http://dx.doi.org/10.1007/s00037-007-0218-9}, } @article {ShaltielUm09, AUTHOR = {Shaltiel, Ronen and Umans, Christopher}, TITLE = {Low-end uniform hardness versus randomness tradeoffs for {AM}}, JOURNAL = {SIAM Journal on Computing}, VOLUME = {39}, YEAR = {2009}, NUMBER = {3}, PAGES = {1006--1037}, ISSN = {0097-5397}, MRCLASS = {68Q15 (68Q10)}, MRNUMBER = {2538848 (2010k:68030)}, MRREVIEWER = {Yongge Wang}, DOI = {10.1137/070698348}, URL = {http://dx.doi.org/10.1137/070698348}, } @ARTICLE{ShaltielUm05, AUTHOR = "Ronen Shaltiel and Christopher Umans", TITLE = "Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator", JOURNAL = "Journal of the {ACM}", YEAR = "2005", volume = "52", number = "2", pages = "172--216" } @Article{LundFoKaNi92, title={Algebraic Methods for Interactive Proof Systems}, author={Carsten Lund and Lance Fortnow and Howard Karloff and Noam Nisan}, area={Complexity Theory}, pages={859--868}, journal=jacm, month=oct, year=1992, volume=39, number=4, source={http://theory.lcs.mit.edu/~jacm/jacm.bib} } @Article{Shamir92, title={{IP} = {PSPACE}}, author={Adi Shamir}, area={Complexity Theory}, pages={869--877}, journal=jacm, month=oct, year=1992, volume=39, number=4, preliminary={FOCS::Shamir1990:11}, source={http://theory.lcs.mit.edu/~jacm/jacm.bib} } @article{ALMSS92, Author = "S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy", Title = "Proof verification and hardness of approximation problems", journal = jacm, Pages = "501-555", volume = 45, number =3, Year = 1998, note = {}, } @Article{AS92, title={Probabilistic Checking of Proofs: A New Characterization of~{NP}}, author={S. Arora and S. Safra}, journal=jacm, pages={70--122}, year=1998, volume=45, number=1, note = {}} @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}, source={http://theory.lcs.mit.edu/~jacm/jacm.bib} } @Article{AroraSa98, title={Probabilistic Checking of Proofs: A New Characterization of~{NP}}, author={Sanjeev Arora and Shmuel Safra}, area={Formal Languages and Complexity Theory}, journal=jacm, pages={70--122}, month=jan, year=1998, volume=45, number=1, keywords={Approximation algorithms, complexity hierarchies, computations on polynomials and finite fields, error-correcting codes, hardness of approximations, interactive computation, NP-completeness, probabilistic computation, proof checking, reducibility and completeness, trade-offs/relations among complexity measures}, general-terms={Algorithms, Theory, Verification}, cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1}, preliminary={focs::AroraS1992}, source={http://theory.lcs.mit.edu/~jacm/jacm.bib} } @incollection {MiltersenViWa99, AUTHOR = {Miltersen, Peter Bro and Vinodchandran, N. V. and Watanabe, Osamu}, TITLE = {Super-polynomial versus half-exponential circuit size in the exponential hierarchy}, BOOKTITLE = {Computing and combinatorics (Tokyo, 1999)}, PAGES = {210--220}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {1999}, MRCLASS = {68Q17}, MRNUMBER = {2000h:68084}, } @article {KarpLi82, AUTHOR = {Karp, Richard M. and Lipton, Richard J.}, TITLE = {Turing machines that take advice}, JOURNAL = {L'Enseignement Math{\'e}matique. Revue Internationale. IIe S{\'e}rie}, VOLUME = {28}, YEAR = {1982}, NUMBER = {3-4}, PAGES = {191--209}, ISSN = {0013-8584}, CODEN = {ENMAAR}, MRCLASS = {68C40 (03D10 94C10)}, MRNUMBER = {84k:68036a}, } @Book{Sipser05, author = {Michael Sipser}, ALTeditor = {}, title = {Introduction to the Theory of Computation}, publisher = {Course Technology}, year = {2005}, OPTkey = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, edition = {2nd}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @article {BabaiFoLu91, AUTHOR = {Babai, L{\'a}szl{\'o} and Fortnow, Lance and Lund, Carsten}, TITLE = {Nondeterministic exponential time has two-prover interactive protocols}, JOURNAL = {Computational Complexity}, VOLUME = {1}, YEAR = {1991}, NUMBER = {1}, PAGES = {3--40}, ISSN = {1016-3328}, CODEN = {CPTCEU}, MRCLASS = {68Q15 (68Q60)}, MRNUMBER = {92h:68031}, MRREVIEWER = {Marius Zimand}, } @article {FeigeGoLoSaSz96, AUTHOR = {Feige, Uriel and Goldwasser, Shafi and Lov{\'a}sz, Laszlo and Safra, Shmuel and Szegedy, Mario}, TITLE = {Interactive proofs and the hardness of approximating cliques}, JOURNAL = {Journal of the ACM}, VOLUME = {43}, YEAR = {1996}, NUMBER = {2}, PAGES = {268--292}, ISSN = {0004-5411}, MRCLASS = {68Q15 (68Q10 68Q25)}, MRNUMBER = {97h:68037}, MRREVIEWER = {Juraj Hromkovi{\v{c}}}, } @incollection {Lu00, AUTHOR = {Lu, Chi-Jen}, TITLE = {Derandomizing {A}rthur-{M}erlin games under uniform assumptions}, BOOKTITLE = {Algorithms and computation (Taipei, 2000)}, PAGES = {302--312}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2000}, MRCLASS = {68Q15 (68Q10)}, MRNUMBER = {1 858 372}, } @article {Kabanets01, AUTHOR = {Kabanets, Valentine}, TITLE = {Easiness assumptions and hardness tests: trading time for zero error}, OPTNOTE = {Special issue: Complexity 2000 (Florence)}, JOURNAL = {Journal of Computer and System Sciences}, VOLUME = {63}, YEAR = {2001}, NUMBER = {2}, PAGES = {236--252}, ISSN = {0022-0000}, CODEN = {JCSSBM}, MRCLASS = {68Q15}, MRNUMBER = {1 867 124}, }