Randomized Algorithms

Emo Welzl, emo"AT"inf.ethz.ch
Bernd Gärtner, gaertner"AT"inf.ethz.ch
Uli Wagner, uli"AT"inf.ethz.ch

(Unfortunately, Christos Papadimitriou had to cancel his planned stay at ETH this fall, so he could not contribute to this course.)

Teaching Assistant

Uli Wagner, uli"AT"inf.ethz.ch

Where and When

Everything will happen in room B42 of the IFW building.
There will be a first meeting on October 2, 11:30am-12:15pm, during which the reading assignments will be distributed (to those who have not printed a copy yet, that is.)
We will meet four times, each time from 10am to 12 (noon, not midnight), to discuss in detail the reading assignments and the exercises therin: On October 8 & 10 for Part 1, and on October 15 & 17 for Part 2.
During the five weeks of October 21 through November 22, the course will be held Mondays and Tuesdays, 9am till 6pm.

Daily Schedule

As a rough schedule, we will start at 9am (9:15, to be precise) with two to three hours of lectures. The afternoon will be devoted to solving exercises. 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: Tuesday, November 26, 9am-12.
Where: ETH Zurich, IFW B 42
Mode: Written exam.

Discussion of the Exam: Wednesday, January 8, 10am-12.

References

Randomized Algorithms

Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press (1995).

The Probabilistic Method

Noga Alon, Joel H. Spencer, The Probabilistic Method, Wiley-Interscience (1992); (second edition, 2000).

Jiri Matousek, Jan Vondrák, The Probabilistic Method, Lecture notes, Department of Applied Mathematics, Charles University Prague (2002).

Joel H. Spencer, Ten Lectures on the Probabilistic Method, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM (1987).

Discrepancy Theory

Jiri Matousek, Geometric Discrepancy - An Illustrated Guide, Algorithms and Combinatorics 18, Springer Verlag (1999).

Bernard Chazelle, The Discrepancy Method - Randomness and Complexity, Cambridge University Press (2000).

Jószef Beck, William E. Chen, Irregularities of Distribution, Cambridge Tracts in Mathematics 89, Cambridge University Press (1987).

LP-type Problems and Unique Sink Orientations of Cubes

Bernd Gärtner and Emo Welzl, Explicit and Implicit Enforcing - Randomized Optimization, Lectures of the Graduate Program Computational Discrete Mathematics, Lecture Notes in Computer Science 2122 (2001), 26-49.

Tibor Szabó and Emo Welzl, Unique Sink Orientations of Cubes, Proc. 42nd Annual IEEE Symp. on Foundations of Computer Science (FOCS 2001), 547-555.

Miscellaneous

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).

Pre-doc Students

Mattias Andersson, mattias"AT"cs.lth.se
Peter Cech, cech"AT"upc.uniba.sk
Nico Galoppo von Borries, scratch"AT"ulyssis.org
Anja Krech, krech"AT"math.fu-berlin.de
Peter Leskovský, leskovs7"AT"kepler.fmph.uniba.sk
Matús Mihalák, mihalak"AT"kopernik.cc.fmph.uniba.sk
Shankar Ram, cheeyam"AT"yahoo.com
Daniel Soll, Soll"AT"stud-mailer.uni-marburg.de
Öznur Yasar, yasaroznur"AT"hotmail.com
Thomas Yan Zhang, cszy"AT"cs.ust.hk

Robert Berke, berker"AT"student.ethz.ch
Raphael Boog, boogra"AT"student.ethz.ch
Ferdinando Cicalese, cicalese"AT"dia.unisa.it
Björn Glauss, glauss"AT"student.ethz.ch
Martin Kutz, kutz"AT"math.fu-berlin.de
Zsuzsanna Lipták, zsuzsa"AT"inf.ethz.ch
Marc Nunkesser, mnunkess"AT"inf.ethz.ch
Morten Hegner Nielsen, mhn"AT"imada.sdu.dk
Leo Ruest, ruestle"AT"student.ethz.ch
Johannes Schneider, schneijo"AT"student.ethz.ch Christoph Schwitter, chs"AT"student.ethz.ch
Arno Wagner, wagner"AT"tik.ee.ethz.ch