Lecture: Discrepancy Theory (2+2 = 6LP)

Topic

Discrepancy theory deals with a number of different looking, though related, problems. Their common theme is `balance' or `irregularities of distributions'. Here are three examples:

Geometric discrepancy problem: Distribute n points in the unit square in such a way that in all axis-parallel rectangles R, the number of points is close to the fair value of area(R) * n.
Combinatorial discrepancy: Color the ground set of a setsystem with two colors in such a way that all sets receive (as good as possible) the same number of points in each color.
Rounding problems: For a given matrix A and a vector x, round x to an integer vector y in such a way that all rounding errors |(Ax)_i - (Ay)_i|,i = 1, ..., m, are small.

Understanding of such problems proves to be highly useful in the development of efficient algorithms, in particular, approximation algorithms, in computational geometry and numerical integration. However, the beauty and wealth of this young area also motivates application independent research.

Audience, Prerequisites, etc.:

In this lecture, I will give an introduction to discrepancies. We will regard the three problems mentioned above as well as game-theoretic aspects. I will try both to give a good survey of this area and to present some of the methods that might be of particular interest. If the participants are interested, a seminar on this subject will be organized next semester.

The lecture is suitable for student of computer science and mathematics. It needs no particular prerequisites. The lecture will be held in English, exams can be done in English or German. Since we will learn a number of very recent results, the lecture is also highly suitable for students interested in starting a master, diploma or PhD project in this area.

Time, Location

Wed 9-11, Building 46.1 (Max-Planck-Institute), Room 022.

Exception! Last week before Christmas and first (semester) week in the new year: Lecture moved to Thursday 11-13 in Room 21.

Exercises

Exercises are organized together with Nils Hebbinghaus. More details here.

Contact

Dr. Benjamin Doerr, MPI, Room 304

Last modified: Fri Dec 16 14:06:48 CET 2005

PS: You need a problem to think about till the lecture starts? No problem. Here is Ulam's liar game: Carole thinks of a number between one and a million. Paul tries to guess it, using Yes/No questions only. In answering these questions, Carole may lie (at most) once. How many questions does Paul need in the worst case?

PPS: You are tired of problems that were already solved? No problem. I have some cool topics for bachelor, master, diploma and PhD theses. Drop in my office and I'll tell you more.