max planck institut
mpii logo Minerva of the Max Planck Society

Random Discrete Structures

Basic Information

Lectures: Wednesday 10:00-12:00, room 024 (ground floor of the MPI-INF building E1.4)
Lecturers: Kunal Dutta and Arijit Ghosh
Tutorials: Friday 10:00-12:00. , E1 5, room 630 (sixth floor of the MPI-SWS building)
Exam dates: TBD


We shall study applications of randomness in computer science and combinatorics.

Prerequisites: An undergraduate course in Algorithms. Mathematical maturity.



Linearity of expectation, moments and derivatives
Tail inequalities, martingales, concentration of measure
Random walks
Markov chains
Probabilistic Methods.


Metric embeddings and dimension reduction.
Lovasz Local Lemma and its algorithmic results.
Computational Geometry: Randomized incremental constructions, Backward analysis.
Random graphs and Percolation.
Dependent Random Choice.



[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.


[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:

[BTI04] A. Blum, Tail inequalities, CMU, 2004.
[BPI04] A. Blum, Probabilistic inequalities, CMU, 2004.
[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.


Date Topics Lecture notes
Apr 15, 22
Apr 25
Apr 30 Probabilistic Inequalities I: Markov's, Chebyshev's inequalities
May 7 Probabilistic Inequalities II: Chernoff Bounds
May 21 Applications of Chernoff Bounds; Azuma's inequality.
May 23 Martingales and Azuma's inequality I.
May 28 Local Lemma: Statements, Proof and Applications
May 30 Local Lemma: Applications, and Moser-Tardos Algorithm Proof
June 4 Local Lemma: Moser-Tardos: contd., Karthik's variant
June 6 Martingales and Azuma's inequality: II


Date Sheet Topics
Apr 25 Tutorial 1 Basics of Probability; Expectation; Alterations
May 27 Tutorial 2 Markov's Inequality, Chebyshev's Inequality, Chernoff Bounds
June 6 Tutorial 2: Correction Markov's Inequality, Chebyshev's Inequality, Chernoff Bounds
June 17 Tutorial 3 Lovasz Local Lemma, Martingales, Azuma's inequality

Final Exam


More Courses of the Algorithms and Complexity Group

Search MPII (type ? for help)