The Fourier Transform in Algorithms and Optimization

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.


Lecture/Exercises: Thursday, 10:15, MA B1 524



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