Lecturer
Description
A (4 ponits) doctoral cours. We will discuss basic tools for analyzing randomized computation,
as well as some, by now, classical results.
Contents
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.
Schedule
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.
Abstract:
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
Contact
Interested people are asked to contact the lecturer at
Jaroslaw
Book
Randomized Algorithms. Rajeev Motwani and Prabhakar Raghavan. ISBN 0-521-47465-5.