Randomized Algorithms

Emo Welzl, emo@inf.ethz.ch
Tibor Szabo, szabo@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, Stirling numbers, abstract optimization frameworks)
Vapnik-Chervonenkis Dimension (range spaces of finite VC-dimension, epsilon-approximations, epsilon-nets, `oversampling'-analysis)
Random Walks (matchings in regular bipartite graphs, derandomization, coloring graphs with no monochromatic triangle, coupling, 2-SAT, 3-SAT, restarts)

Where and When

The course will takes in room B42 of the IFW building (consult map). During the five weeks of October 23 through November 26, 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

Tuesday, Nov 28, 9:00-12:00, B42 (IFW), written exam; material: lectures, exercises, reading assignments; books, notes, etc. allowed, (but no electronic devices).
The exam problems.
Discussion of exam, Thursday, Dec 7, 10:00 - 12:00, B42 (IFW)

Dates (and Exceptions from Schedule above)

Wednesday, Oct 4, 14:00, B42 - Handing out reading assignment, part I.
Thursday, Oct 12, 10:00(-12), B42 - Discussion of part I, and handing out reading assignment, part II.
Friday, Oct 13, 10:15(-12), B42 - Discussion of part I, cont'd.
Thursday, Oct 19, 10:15(-12), B42 - Discussion of part II.
Monday, Oct 23, 9:15, B42 - lectures start.
Monday, Nov 6, 15:30 - 16:10, B42, discussion of exercises (16:15 Talk by Ron Rivest)
Monday, Nov 20, no discussion of exercises (15:15 Symposium with O.-J. Dahl, B. Stroustrup and N. Wirth).
Tuesday, Nov 21, 9:15 - 10:00, discussion of exercises.
Tuesday, Nov 21, 10:15 - 12:00, last lecture.
Tuesday, Nov 28, 9:00 - 12:00, exam.
Thursday, Dec 7, 10:00 - 12:00, discussion of exam.

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

Participants

provided by Hiroyuki Miyazawa - click picture for enlargement

Pre-Doc students

Sai Anand, India, r_saianand@yahoo.com
Giovani Gomez, Mexico, ggomez@iiic.ethz.ch
Godfrey Njulumi Justo, Tanzania, justo@iiic.ethz.ch
Hiroyuki Miyazawa, Japan, miyazawa@iiic.ethz.ch
Ingo Schurr, Germany, schurr@iiic.ethz.ch
Stefanakos Stamatis, Greece, stefanak@iiic.ethz.ch
Frank Vallentin, Germany, vallenti@iiic.ethz.ch

Other Participants

Sabine Cornelsen, Konstanz, Germany, sabine.cornelsen@uni-konstanz.de
Michael Gatto, Zurich, Switzerland, mgatto@iiic.ethz.ch
Thomas Herrmann, Zurich, Switzerland, herrmann@ifor.math.ethz.ch
Dominic Jost, Zurich, Switzerland, djost@iiic.ethz.ch
Carsten Lange, Berlin, Germany, clange@math.tu-berlin.de
Martin Mächler, Zurich, Switzerland maechler@stat.math.ethz.ch
David Orden, Santander, Spain, ordend@matesco.unican.es
Julian Pfeifle, Berlin, Germany, pfeifle@math.tu-berlin.de
Stefano Picozzi, Lausanne, Switzerland, stefano.picozzi@epfl.ch
József Solymosi, Zurich, Switzerland, solymosi@inf.ethz.ch
Csaba Dávid Tóth, Zurich, Switzerland, toth@inf.ethz.ch
Danica Vukadinovic, Zurich, Switzerland, vukadin@tik.ee.ethz.ch
Thomas Willhalm, Konstanz, Germany, thomas@willhalm.de
Uli Wagner, Zurich, Switzerland, uli@inf.ethz.ch

For sending email to all email addresses listed above: cgc_randalgs_stud@inf.ethz.ch