skip to content

Discrete Analysis

Participation in INI programmes is by invitation only. Anyone wishing to apply to participate in the associated workshop(s) should use the relevant workshop application form.

8th January 2011 to 8th July 2011
Keith Ball University College London
Franck Barthe [IMT, Toulouse], Université de Toulouse
Ben Green [Cambridge], University of Cambridge
Assaf Naor [New York], New York University


Programme Theme

During the past decade or so there have been dramatic developments in the interaction between analysis, combinatorial number theory and theoretical computer science: specifically between harmonic analysis and combinatorial number theory and between geometric functional analysis and the theory of algorithms.

Not only have discoveries in one area been used in others but, even more strikingly, there has emerged a commonality of methods and ideas among these apparently diverse areas of mathematics. The use of harmonic analysis in number theory is at least a century old, but in the recent works of Gowers, Green and Tao and others on the existence of arithmetic progressions in subsets of the integers, and in particular the sequence of primes, it has developed into an entire area: additive combinatorics. Classical inequalities of harmonic analysis, such as the isoperimetric inequality, have discrete analogues that are often more subtle than the continuous versions and have wide-ranging applications: for example the discrete isoperimetric inequality of Talagrand, which inspired his work on spin-glass models.

Through the study of the influence of variables on Boolean functions, discrete harmonic analysis has started to play a crucial role in theoretical computer science. And at the same time it has become clear that many problems in theoretical computer science and combinatorial optimisation are actually geometric problems in "disguise". In other cases, the problems are so complex that the best available approximation algorithms were devised by embedding the underlying combinatorial structure into a familiar geometry (such as Euclidean space) so that it becomes "geometrically obvious" what to do.

The purpose of this programme is to bring together researchers in these diverse areas of mathematics, to encourage more interaction between these fields, and to provide an opportunity for UK mathematicians to engage with an important part of the mathematical computer science community.

Final Scientific Report: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons