ATHENS 2021 ‑ Randomized Algorithms (CTU23)

November 15-19

Lecturer: Jan Volec

Course starts: Mo 15.11, 9:00

Location: Room T214 at Trojanova 13, 120 00 Prague (Faculty of Nuclear Engineering and Physical Sciences, Czech Technical University)

Covered topics: Probabilistic Method, Karger-Stein's Algorithm, Method of conditional probabilities, Lovasz Local Lemma, Entropy compression and Moser-Tardos Algorithm.

Course notes: TBA

References: Randomized Algorithms by Motwani & Raghavan, The Probabilistic Method by Alon & Spencer.

Course schedule

DayPart 1 ‑ LecturePart 2 ‑ Exercises
Mo 15.119:00-12:00   Introduction, Basic applications of Probabilistic Method13:30-15:00
Tu 16.119:00-12:00   Method of conditional probabilities, Karger's Algorithm15:30-17:00
We 17.119:00-12:00   Karger-Stein's Aglorithm, Lovasz Local Lemma (symmetric form)15:15  Excursion to Technical Museum (map)
Th 18.119:00-12:00   Lovasz Local Lemma (general form)15:40-17:00
Fr 19.119:00-12:00   Entropy compression and Moser-Tardos Algorithm13:30-14:30   Q&A   14:30-15:30 Final Test

Farewell dinner: Fr 19.11 17:00-20:00 at Rector's office (Jugoslavských partyzánů 3; see Google maps)