max planck institut

informatik

informatik

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 |