Random Discrete Structures (MPI, Summer 2014)
Random Discrete Structures (MPI, Summer 2014)
Instructors Kunal Dutta and Arijit Ghosh
Description Study applications of randomness in computer science and combinatorics
Prerequisites Undergraduate course in algorithms and mathematical maturity
Schedule Lectures on Wednesday 10-12, Room 024, E1 4 building, and tutorials on Friday 10-12, Room 630, E1 5 building
Syllabus
Tools
Linearity of expectations, moments, and derivatives
Tail inequalities, martingales, concentration of measures
(Markov and Chebyshev inequalities, and Chernoff type bounds)
Random walks, and its applications
Markov chains
Probabilistic methods
Applications
Metric embeddings and dimension reduction
(Johnson-Lindenstrauss lemma, Bourgain embedding, Bartal's result)
Lovasz local lemma and its algorithmic results
Computational geometry: Randomized incremental constructions, backward analysis
Discrepancy
Dependent random choices
Random graphs and percolations
References
Main
[MU05] M. Mitzenmacher and E. Upfal, Probability and Computing, Cambridge Univ. Press, 2005.
[AS08] N. Alon and J. Spencer, The Probabilistic Method, 2nd ed. Wiley, 2008.
Additional
[MR95] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[B00] B. Bollobas, Random Graphs, 2nd ed. Academic Press, 2000.
[JLR00] S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley, 2000.
Note that [MU05], [AS08], [MR95], [B00], and [JLR00] have been reserved in the library for this course. Online courses, lecture notes, and papers are relevant for this course.
[BTI04] A. Blum, Tail inequalities, CMU, 2004.
[BPI04] A. Blum, Probabilistic inequalities, CMU, 1998.
[H-P14] S. Har-Peled, Randomized Algorithms, UIUC, 2014.
[CL13] L. C. Lau, Randomness and Computation, CUHK, 2013.
[WTG10] W. T. Gowers, Two Cultures of Mathematics.
[RRC14] R. Rubinfeld, Randomness and Computations, MIT, 2014.
[SMC09] A. Sinclair, Markov Chain Monte Carlo: Foundations and Applications, UC Berkeley, 2009.
[SRC11] A. Sinclair, Randomness and Computation, UC Berkeley, 2011.