Prof. Emo Welzl and Prof. Bernd Gärtner
Emo Welzl, email@example.com
Tibor Szabo, firstname.lastname@example.org
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.
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.
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.
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).
Sai Anand, India, email@example.com
Giovani Gomez, Mexico, firstname.lastname@example.org
Godfrey Njulumi Justo, Tanzania, email@example.com
Hiroyuki Miyazawa, Japan, firstname.lastname@example.org
Ingo Schurr, Germany, email@example.com
Stefanakos Stamatis, Greece, firstname.lastname@example.org
Frank Vallentin, Germany, email@example.com
Sabine Cornelsen, Konstanz, Germany, firstname.lastname@example.orgEmail List
Michael Gatto, Zurich, Switzerland, email@example.com
Thomas Herrmann, Zurich, Switzerland, firstname.lastname@example.org
Dominic Jost, Zurich, Switzerland, email@example.com
Carsten Lange, Berlin, Germany, firstname.lastname@example.org
Martin Mächler, Zurich, Switzerland email@example.com
David Orden, Santander, Spain, firstname.lastname@example.org
Julian Pfeifle, Berlin, Germany, email@example.com
Stefano Picozzi, Lausanne, Switzerland, firstname.lastname@example.org
József Solymosi, Zurich, Switzerland, email@example.com
Csaba Dávid Tóth, Zurich, Switzerland, firstname.lastname@example.org
Danica Vukadinovic, Zurich, Switzerland, email@example.com
Thomas Willhalm, Konstanz, Germany, firstname.lastname@example.org
Uli Wagner, Zurich, Switzerland, email@example.com
For sending email to all email addresses listed above: firstname.lastname@example.org