## DOCCOURSE PRAGUE 2006## Programme for pre-doctoral and doctoral students in## Combinatorics, Geometry, and Computation## Prague, January 5 - March 31, 2006 |

Supported by the EU network COMBSTRU and by DIMATIA Prague.

Organized in coordination with Predoc-Course Berlin 2006, April-June 2006.

DIMATIA Centre at the Charles University Prague offers a three month study programme for PhD students and students preparing to enter a PhD programme in areas: Combinatorics and Graph Theory; Discrete and Computational Geometry; Combinatorial Optimization; Discrete Structures.

Information about the previous DOCCOURSEs in Prague, which had about 25 participants and which we believe were quite successful, can be found here and here.

The programme in 2006 includes a five-week research-oriented course
on harmonic analysis in computer
science and combinatorics (speakers: **Gil Kalai and
Nathan Linial**;
see below for more details), complemented by additional lectures
on related topics, and individual research projects.

The contact persons and the leaders of the programme are J. Matousek and J. Nesetril (both Charles University, Prague).

**Abstract:**

Harmonic Analysis (often also called Fourier Analysis) is a classical field of mathematics. It originated in mathematical physics when Joseph Fourier sought to develop a mathematical theory of heat. It was later discovered to be a field rich in theory and extremely flexible and versatile in applications. It is a mainstay for all of mathematical physics. It has become one of the main parts of mathematical analysis and has found many applications in number theory. It also interacts beautifully with group theory and other parts of algebra.

In recent years it has been discovered that Harmonic Analysis can also be very useful in discrete mathematics and theoretical computer science. The purpose of this course is thus twofold: To offer a quick introduction to the classical theory and to show some of these more recent applications. We start with the classical theory since this is the most developed exemplar of the general theory. Also, it is a good source of inspiration when you try to push further the frontiers of the theory and when you seek new applications. The spectrum of possible applications in discrete mathematics seems very broad and many of these developments are still at an early stage, so it's not overly difficult to start doing research in these areas on one's own.

Special focus will be given to the study of Boolean functions f:{0,1}^n
-->{0,1}, where discrete harmonic analysis has been very successful.
Some basic complexity measures such as how strongly a single variable
*influences*
a function, the *noise sensitivity* of a function, have very
clean and powerful Fourier expressions. In the study of Boolean functions, a
sample meta-question is
"what types of conditions guarantee that a given function really only depends
on a few coordinates ?"
Variants of this question turn out to play an important role in some
computer-science results (e.g., in Probabilistically Checkable Proofs).

Among the nice aspects of this area is that at least the classical theory is described beautifully in a number of books that combine crisp mathematical presentation with a broad range of applications as well as many entertaining stories and historical anecdotes. Enjoy!

**Background:** No special prerequisites besides the
basic undergraduate mathematics, including
some combinatorics and graph theory.

**Bibliography:**

- Korner's "Fourier Analysis" is a good general reference.
- Offner's "A Little Harmonic Analysis" is short and available here.
- The following are good reads. All have similar names involving the words "Fourier" or "Harmonic" so only the authors are listed.
- Dym & McKean
- A. Terras (1st Volume)

- The following are good reference books but not best for recreational reading.
- Y. Katznelson
- Helgason

- Error-correcting codes
- van Lint "Coding Theory"

- Orthogonal polynomials
- Davis "Interpolation and Approximation"
- Szegö "Orthogonal polynomials"

The course will be accompanied by additional lectures on related topics by other people invited to Prague.