Randomized Algorithms

Emo Welzl, emo"AT"inf.ethz.ch

Assistant

Csaba David Toth, toth"AT"inf.ethz.ch

Topics (and Keywords)

Discrepancy (large cuts in graphs, combinatorial discrepancy, discrete approximations of distributions, Chernoff bounds, derandomization, Hadamard matrices, small sampling spaces, pairwise independence, jittered sampling, spanning paths of small stabbing number, iterative reweighting, Beck-Fiala Theorem)
Geometric Optimization (linear programming, smallest enclosing balls, backwards analysis, iterative reweighting, downscaling by sampling, implicit enforcing techniques, subexponential optimization, abstract optimization frameworks, LP-type problems, unique sink orientations)
Vapnik-Chervonenkis Dimension (range spaces of finite VC-dimension, epsilon-nets, `oversampling'-analysis)

Where and When

The course will takes in room B42 of the IFW building (consult map). During the five weeks of October 22 through November 25, the course will be held Mondays and Tuesdays, 9am till 6pm.

Schedule

For a rough schedule, we start 9:15 in the morning with two to three hours of lectures. After lunch exercises are worked out. The day is concluded by a discussion of material and exercises, 5-6pm on Mondays, and 4-5pm on Tuesdays.

Reading Assignments

Basic Examples of Probabilistic Analysis, Part I and Part II.

Exam

When: Thursday, Nov 29, 9:00 - 11:45 (it's 9:00 sharp!).
Where: ETH Zurich - IFW B42, and TU Berlin - MA 6-2, Str. des 17. Juni 136.
Mode: written exam.
Material: lectures, exercises, reading assignments.
You can take along: books, notes, (but no electronic devices, not even a pocket calculator).
Discussion of exam: Dec 4, 10:15 - 11:45, IFW B42.
Here are the exam problems.

Thursday, Oct 11, 10:15-12:00, Discussion Exercises, Part I
Friday, Oct 12, 10:15-12:00, cont'd
Friday, Oct 12, 14:00-16:00, cont'd
Monday, Oct 15, 14:15-16:00, cont'd
Thursday, Oct 18, 10:15-12:00, Discussion Exercises, Part II
Friday, Oct 19, 10:15-12:00, cont'd
Monday, Oct 22, 9:15, beginning of lectures

Some Books

Noga Alon, Joel H. Spencer, The Probabilistic Method, Wiley-Interscience (1992); (second edition, 2000).
Jószef Beck, William E. Chen, Irregularities of Distribution, Cambridge Tracts in Mathematics 89, Cambridge University Press (1987).
Bernard Chazelle, The Discrepancy Method - Randomness and Complexity, Cambridge University Press (2000).
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics - A Foundation for Computer Science, Addison-Wesley (1989).
Rainer Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner Series in Computer Science, (1984).
Jiri Matousek, Geometric Discrepancy - An Illustrated Guide, Algorithms and Combinatorics 18, Springer Verlag (1999).
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press (1995).
Joel H. Spencer, Ten Lectures on the Probabilistic Method, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM (1987).

Pre-Doc students participating

Debjani Bhowmick, debjanib"AT"iiic.ethz.ch
Paz Carmi, carmi"AT"iiic.ethz.ch
Peter Csorba, pcsorba"AT"iiic.ethz.ch
Michael Eisenring, michaeei"AT"iiic.ethz.ch
Kaspar Fischer, kfischer"AT"iiic.ethz.ch
Vojtech Franek, franek"AT"iiic.ethz.ch
Yoshio Okamoto, okamotoy"AT"iiic.ethz.ch
Shahid Rahman, shahidur"AT"iiic.ethz.ch
Thomas Schank, schank"AT"iiic.ethz.ch
Milos Stojakovic, smilos"AT"iiic.ethz.ch
Franciscus Wessendorp, fwessend"AT"iiic.ethz.ch

Other Participants

Manuel Bodirsky, bodirsky"AT"informatik.hu-berlin.de
Francesco Borrelli, borrelli"AT"aut.ee.ethz.ch
Svetlana Domnitcheva, domnitch"AT"inf.ethz.ch
Alexander Hall, hall"AT"tik.ee.ethz.ch
Vanessa Kaeaeb, kaeaeb"AT"math.TU-Berlin.DE
Katharina Langkau, langkau"AT"math.TU-Berlin.DE
Shi Lingsheng, shi"AT"informatik.hu-berlin.de
Heiko Schilling, schillin"AT"math.TU-Berlin.DE
Johan Sjoedin, d98-jsj"AT"nada.kth.se
Bettina Speckmann, speckmann"AT"inf.ethz.ch
Arnold Wassmer, wassmer"AT"math.TU-Berlin.DE
Birgitta Weber, weberb"AT"inf.ethz.ch