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.

Discrepancy

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.

[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

here