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