ATHENS 2025 ‑ Randomized Algorithms (CTU23)

November 17-21, 2025

Lecturer: Jan Volec

Tutor: Alexander Clifton

Course starts: Mo 17.11, 9:00

Location: Dejvice campus – FEL, Technická 1902/2, 160 00 Prague (Faculty of Electrical Engineering, Czech Technical University)

Room: T2:H1-130

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

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


Course schedule

DayPart 1 ‑ LecturePart 2 ‑ Exercises
Mo 17.119:30-12:30   Introduction, Basic applications of Probabilistic Method14:00-15:30
Tu 18.119:30-12:30   Method of conditional probabilities, Karger's Algorithm14:00-15:30
We 19.119:30-12:30   Karger-Stein's Aglorithm, Lovasz Local Lemma (symmetric form)N/A
Th 20.119:30-12:30   Lovasz Local Lemma (general form)14:00-15:30
Fr 21.119:30-12:30   Entropy compression and Moser-Tardos Algorithm14:00-14:25   Q&A   14:30-15:30 Final Test

We 19.11 15:15 – Excursion to Technical Museum (Kostelní 42, 170 00 Prague; see Google maps)

Fr 21.11 17:00-19:00 – Farewell dinner at Rector's office (Jugoslavských partyzánů 3, 160 00 Prague; see Google maps)