Syllabus
Martingales, Azuma inequality.
Talagrand inequality.
Poisson paradigm -- Janson inequality and Brun sieve.
Quasirandomness.
Random graphs.
Multi-phase random processes (iterative coloring of sparse graphs).
Annotation
Probabilistic method is a way to prove existence of objects by counting: in a suitable probability space one shows that with nonzero probability we get the desired object.
This class is a continuation of Probabilistic Techniques NTIN022 where the basic techniques were described. (The knowledge of those is necessary to follow this class.) In this class we will extend and deepen these techniques.
The class is complementing (but not overlapping) with Probabilistic algorithms NDMI025.