Provide an introduction to topics at the intersection of probability, discrete mathematics, and theoretical computer science. The focus of the course will be both on the mathematical methods necessary for the analysis of algorithms, and on models and examples inspired by problems of a computer science and combinatorial nature.
teacher profile teaching materials
- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Programme
Methods:- Probabilistic method (first moment method, second moment method, Lovász Local Lemma)
- Concentration bounds (e.g., Chernoff, Hoeffding, Bernstein, Azuma, McDiarmid inequalities)
- Pairwise independence
- Martingales (introduction, cf. CP410)
- Markov chains (introduction, cf. CP420)
Models and examples:
- Randomized algorithms and average-case analysis (e.g., quicksort, routing on sparse networks, Johnson–Lindenstrauss, balls-into-bins, hashing functions, Prophet/Secretary inequalities, randomized rounding, stochastic bandits)
- Random graphs (e.g., Erdős–Rényi and preferential attachment)
- Random walks on graphs (e.g., PageRank, cover times, Wilson’s algorithm)
- Stochastic multi-agent systems (e.g., contact process, voter model)
Core Documentation
The lectures will be based primarily on the following books:- Michael Mitzenmacher e Eli Upfal, Probability and computing: randomized algorithm and probabilistic analysis
- Noga Alon e Joel Spencer, The probabilistic method
- Sebastién Roch, Modern discrete probability: an essential toolkit
At the end of each lecture, the corresponding notes will be shared with the students.
Reference Bibliography
Other reference books: - David Levin e Yuval Peres, Markov chains and mixing times - Rajev Motwani e Prabhakar Raghavan, Randomized algorithms - Devdatt Dubhashi e Alessandro Panconesi, Concetration of measure for the analysis of randomized algorithmsAttendance
Lectures will be held three times a week, two hours each (for a total of 30 lectures). Attendance is not mandatory.Type of evaluation
The oral exam will cover the topics presented in class.