The Fourier transform is becoming a standard tool in the toolbox in algorithms. This PhD course provides an introduction to the Fourier transform and some of its applications in the domain of algorithms and combinatorics.
The course is seminar style. This means that every registered PhD student will present a topic in a 60 min lecture, select exercises and host an exercise session in the following week, where the problems are discussed.
Schedule:
Lecture/Exercises: Thursday, 10:15, MA B1 524
Reading:
- I. Kantor, J. Matousek and R. Samal: Mathematics++, Chapter 3, AMS
- O. Reghev: Lattices in Computer Science, Lecture Notes
- T. Rothvoss: Integer Optimization and Lattices
Lectures:
| October 11. | Fritz | Introduction to Fourier Transformation |
| October 18. | Dániel | Arithmetic Progression and Roth’s Theorem |
| November 1. | Moritz | Linearity Testing, Convolution |
| November 22. | Igor | Poisson Summation, the KKL Theorem |
| November 29. (prefered) | Marek | Discrepency of Random Sets |
| December 06. | Christoph | GapCVP (n^{1/2}) is in NP and coNP |
(?) Fritz – Banaszczyk’s Transference Bound