Fourier-Analytic Methods in Discrete Mathematics

(251-1401-00L) WS06/07

Lecturers

Tibor Szabó,	CAB G31.2,	Tel: 044 632 08 58,		.
Uli Wagner,	CAB G33.2,	Tel: 044 632 73 39,		.

Time & Place

Lecture:	Tuesdays 10:15-12:00,	CAB G59.
Exercises:	Tuesdays 9:15-10:00,	CAB G57.

Course Description

We introduce the basics of Fourier analysis on finite abelian groups and discuss applications in Theoretical Computer Science and Combinatorics. These include: bounds for error correcting codes, threshold phenomena in random graphs, voting schemes and influences in Boolean functions, probabilistically checkable proofs, Fermat's Last Theorem over finite fields.

Outlook

In Spring, 2007, there will be a course "Extremal Combinatorics" (here is the course webpage from last year) which follows up on the material covered in the last lecture ("Ramsey- and Turán-type constructions").

We are planning a course on "Threshold Phenomena and Phase Transitions in Computer Science" in Spring, 2008.

Exam

There will be an oral exam of 30 minutes during the examination period. You will be given two questions (e.g., about the proofs of some of the theorems covered in class) and 15-20 minutes to prepare a detailed answer.

Literature

There is no textbook that covers the material, but there are several sets of lecture notes available online:

• Irit Dinur and Ehud Friedgut, Analytical Methods in Combinatorics ad Computer Science, scribe notes for a course taught at the Hebrew University in Jerusalem in Fall 2005.
• Nati Linial, Harmonic Analysis and Combinatorial Applications, scribe notes for a course taught at the University of Washington in Winter 2005.
• László Babai, The Fourier Transform and Equations over Finite Abelian Groups, lecture notes.

Course Material

Our typed lecture notes are not (yet) complete. Thanks to Andreas Razen and Philipp Zumstein for agreeing to make their handwritten notes available in the meantime.

Lecture Notes	A partial set of typed notes; as of yet, without the proof of the BKKL Theorem and the nonuniform version of the KKL Theorem.
Proof of the BKKL Theorem	Notes taken by Philipp Zumstein
Threshold Phenomena alternative version	Notes taken by Andreas Razen and Philipp Zumstein.
Fermat's Last Theorem over finite fields and norm graphs	Notes taken by Andreas Razen and Philipp Zumstein.