Pseudorandomness bootcamp

Fundamental techniques in pseudorandomness

• Oded Goldreich. Pseudorandom Generators: A Primer, AMS, 2010. http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf
• Salil Vadhan. Pseudorandomness, Foundations and Trends in Theoretical Computer Science: Vol. 7: No. 13, pp 1-336, NOW publishers, 2012. http://people.seas.harvard.edu/~salil/pseudorandomness/
• Mark Braverman. Polylogarithmic independence fools AC0 circuits. JACM Volume 57 Issue 5, June 2010. http://dl.acm.org/citation.cfm?id=1754401

Extractors and expanders

• S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006), 439-561. http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
• D. Zuckerman. Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory of Computing, 3 (2007): 103-128. http://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf
• V. Guruswami, C. Umans, and S. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes, Journal of the ACM, 56(4):1-34, 2009. https://www.cs.cmu.edu/~venkatg/pubs/papers/PV-condenser.pdf
• E. Chattopadhyay and D. Zuckerman. Explicit two-source extractors and resilient functions, 48th Annual ACM Symposium on Theory of Computing (STOC), pp. 670-683, 2016. https://eccc.weizmann.ac.il/report/2015/119/
• A. Ben-Aroya, D. Doron, and A. Ta-Shma.Explicit two-source extractors for near-logarithmic min-entropy. https://eccc.weizmann.ac.il/report/2016/088/
• Z. Dvir, Extractors for varieties, Computational Complexity, 21:515-572, 2012. https://www.cs.princeton.edu/~zdvir/papers/Dvir08.pdf

Pseudorandom generators

• Salil Vadhan. Pseudorandomness, Foundations and Trends in Theoretical Computer Science: Vol. 7: No. 13, pp 1-336, NOW publishers, 2012. http://people.seas.harvard.edu/~salil/pseudorandomness/
• Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d, Computational Complexity, vol. 18, num. 2, pp. 209-217, 2009 Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2008. http://www.ccs.neu.edu/home/viola/papers/d.pdf

Pseudorandomness and regularity in graphs

• Michael Krivelevich and Benny Sudakov. Pseudo-random Graphs. In More Sets, Graphs and Numbers (Vol. 15, pp. 199262). Springer Berlin Heidelberg. https://www.math.ethz.ch/~sudakovb/pseudo-random-survey.pdf
• David Conlon, Jacob Fox, Yufei Zhao. Extremal results in sparse pseudorandom graphs, Adv. Math. 256 (2014), 206-290 https://arxiv.org/abs/1204.6645
• David Conlon, Jacob Fox, Yufei Zhao. The Green-Tao theorem: an exposition, EMS Surv. Math. Sci. 1 (2014), 249-282. https://arxiv.org/abs/1305.5440
• David Conlon, Jacob Fox. Graph removal lemmas. https://arxiv.org/abs/1211.3487

Arithmetic applications of pseudorandomness

• Ben Green. Montréal notes on quadratic Fourier analysis. In Additive combinatorics, Vol. 43, pp. 69102. Amer. Math. Soc., Providence, RI (2007). https://arxiv.org/pdf/math/0604089v2.pdf
• Julia Wolf. Finite field models in arithmetic combinatorics–ten years on. Finite Fields and Their Applications, 32, 233274 (2015). http://www.juliawolf.org/research/preprints/ffsurveyweb.pdf
• Thomas Bloom’s reading rack on the polynomial method: https://people.maths.bris.ac.uk/~matfb/polynomial.html