Randomized Algorithms


A (4 ponits) doctoral cours. We will discuss basic tools for analyzing randomized computation,
as well as some, by now, classical results.


In this course we will introduce the model of randomized computation and study standard methods for analyzing its outcome. This includes Markov, Chebyshev and Chernoff inequalities as well as the probabilistic method, and the method of conditional expectations. In this part of the course we will follow the book “Randomized Algorithms” by R. Motwani and P. Raghavan.

Next, we will look at some important randomized algorithms in the domains of approximation (max cut, facility location) and online algorithms (k-server, paging). We shell also discuss a method of randomized dependent rounding, which given a fractional vector returns a random integral vector which resembles important properties of the fractional input. This part will be mainly based on research papers.


There will be one lecture and one exercise session per week.

Lecture –  Wednesday 10:15 – 12:00 room AAB 032 (first meeting September 16)
Exercises – Tuesday 15:15 – 17:00 room AAB 032 (first meeting September 22)

In the comming weeks:

1) (16.09) An introduction. Why randomized QuickSort works. Monte Carlo vs. Las Vegas algorithms.
     exercises for 22.09

2) (23.09) Model of randomized computation. Complexity classes RP,PP,BPP,ZPP
     exercises for 29.09

3) (30.09) Markov and Chebyshev Inequalities
     exercises for 06.10

4) (07.10) The Chernoff Bound

4′) (13.10) A talk by Rado presenting “Conflict-Free Coloring for Rectangle Ranges
Using ˜O (n^382+eps) Colors” by Deepak Ajwani, Khaled Elbassioni, Sathish Govindarajan,
Saurabh Ray.

5) (14.10) Randomized approximation algorithms, derandomization via conditional expectation, MAX-SAT, MAX-CUT.
  exercises for 20.10

6) (21.10) Randomized LP-rounding approximation algorithms for facility location.

7) (28.10) Algorithm of Goemans and Williamson for the MAX-CUT problem.

7′) (03.11) A talk by Filip: “Geometric approach to betweenness”

8) (04.11) Dependent randomized rounding.

8`) (10.11) A talk by Nicolai: Random Walk algorithm for 3-SAT

9) (11.11) Introduction to IP and PCP
exercises for 24.11

10) (25.11)  PCP theorem by gap amplification.

10`) (01.12) A talk by Nicolai

11) (02.11) PCP theorem, part 2. Recuction of the alphabet size, assignment testers.
12) (09.11) Online algorithms


Interested people are asked to contact the lecturer at
Jaroslaw Byrka EPFL CH


Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. ISBN 0-521-47465-5.