DOCCOURSE PRAGUE 2006Programme for pre-doctoral and doctoral students inCombinatorics, Geometry, and ComputationPrague, January 5 - March 31, 2006 |
Supported by the EU network COMBSTRU and by DIMATIA Prague.
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:
The course will be accompanied by additional lectures on related topics by other people invited to Prague.