MRTN-CT-2004-511953 | Organisation |
PHENOMENA IN HIGH DIMENSIONS |
Presentation |
---|
Country |
France |
Great Britain |
Germany |
Hungary |
Greece |
Poland |
Spain |
Italy |
Austria |
France |
Germany |
Israel |
Ukraine |
Node |
Marne-la-Vallée |
London |
Kiel |
Budapest |
Athens |
Warsaw |
Zaragoza |
Florence |
Vienna |
Toulouse |
Freiburg |
Tel Aviv |
Kharkov |
Pierre et Marie Curie
Lille Ecole Polytechnique Créteil IHES |
Cambridge
Edinburgh Lancaster Leeds Oxford |
Kiel
Jena Oldenburg |
Budapest, Rényi Institute Budapest, ELTE |
Heraklion
Aegean Athens |
Warsaw | Zaragoza
Sevilla Madrid Murcia Valencia |
Florence
I. per le Applicazioni del Calcolo Modena Uni. ``Cattolica'',Milan Polytechnic Univ.,Milan University of Trieste |
Vienna
Magdeburg Salzburg |
Toulouse
Lyon Nice Sofia-Antipolis |
Freiburg
Karlsruhe Munich |
Tel Aviv
Weizmann Institute Technion (Haifa) Haifa University |
Institute for Low Temperature
Kharkov State University |
Over the last 20 years there has been a dramatic growth in our understanding
of phenomena that occur in high-dimensional systems: those whose characteristic
behaviour appears as the number of variables grows to infinity. Such systems
occur in a wide variety of branches of mathematics and adjacent sciences,
in particular, physics and computing. It is clear that the ability to describe
basic features of such systems mathematically, will be increasingly important
in the life sciences as well, during the next decade.
Numerical simulations and theoretical analyses have revealed two characteristic features of high-dimensional phenomena which can be described as ``unexpected uniformity'' and ``sharp discontinuity''. Historically, these characteristics appeared first in random settings, especially in probability (various forms of the law of large numbers and other limiting theorems), and in statistical physics, where systems of particles, described by the Gibbs distribution, exhibit phase transitions: sudden qualitative changes in behaviour as a result of small changes in parameters. It has become increasingly clear that what underlies these effects is not randomness itself but rather a broader concept of high-dimensionality. High-dimensional systems occurring naturally exhibit random-like behaviour.
The recognition of this occurred almost simultaneously in several fields: high-dimensional geometry and combinatorics as well as probability and statistical physics themselves. Until recently, these branches of mathematics were considered quite separate; and this impeded the exchange of ideas and methods even though the problems and methods were inherently related.
The goal of this project is to bring together researchers in the areas of geometry, analysis, combinatorics, mathematical physics and probability in which these phenomena have emerged and have been studied, and thereby to provide young scientists with a considerably wider understanding of the unity of the respective mathematical ideas. Among the most senior scientists in the programme are many of the architects of the last 20 years' developments; for example, Alon, Gowers, Gromov, Lovász, Milman, Pastur, Pisier, Talagrand and Tsirelson.
While the achievements of the last 20 years have been impressive, there are
serious reasons to believe that we are poised to provide a strikingly clearer
picture of how to handle high-dimensional phenomena in the areas in question:
for example, Talagrand has just solved the long-standing problem on
the form of the free energy in the
Sherrington-Kirkpatrick model of spin glasses. His work depends heavily on
deviation estimates originally discovered in probabilistic and geometric settings.
It should be noted that this direction of mathematical statistical physics
was initiated by works of participants of the Ukrainian team in the early
90's.
Although the members of the network come originally from different mathematical
disciplines and their subjects may seem somewhat fragmented, their works are
linked by a common experience of high-dimensional phenomena and more importantly
by a commonality of methods which have been found to be applicable in all
these areas. A fundamental example is that of concentration principles, which
underly a majority of themes of this program, and which guarantee that within
apparently diverse
families, almost all members look similar: that there is a universal ``type''
which is mimicked by almost all members. Examples of this are the self-averaging
properties in random matrix theory and statistical physics of disordered spin
systems, the concentration phenomenon in geometry as exemplified by Dvoretzky's
theorem and later work in the same direction, and the recent appearance of
limit shapes for random bodies. Quantitative measures of concentration are
essential for randomised computation: they are, in effect, the definition
of geometric expanders and recently they were found to imply strong quantitative
results concerning entropy growth in the central limit theorem.
Project objectives
This project arises from the confluence of several branches of mathematics.
The objectives of the project are supplied by these different branches but
should be understood as part of an overall goal: to understand the appearance
of ``unexpected uniformity'' and ``sharp discontinuity'' in high-dimensional
structures. The six main areas of the programme are as follows:
Researchers in the area of Asymptotic Geometric Analysis will continue
the search for phase transitions and threshold behaviour in high-dimensional
normed spaces:
in particular, in the study of the linear structure of such spaces. A number
of remarkable results in this direction were discovered by the group in
recent years but they look to be
just the ``tip of an iceberg''. For the first time there is now an opportunity
to attack the so-called ``slicing problem'' (which goes back to Bourgain
in the 80's), one of the most
notorious problems in Asymptotic Convexity. (The problem has many equivalent
formulations: one such is that the geometric average of the principal moments
of inertia of a convex body of volume 1, is bounded independently of the
dimension and the body). Progress on this problem by Milman, his
student Klartag and Bourgain has opened a new avenue in this direction.
A related and extremely intriguing issue which is attracting significant
attention concerns the ``Central Limit Properties of Convex Bodies''. One
form of the question is whether every isotropic convex body of high enough
dimension has a direction in which the projection of its volume is close
to a Gaussian distribution. There is an obvious link with classical probability
here but the real point is to see the classical central limit theorem as
a reflection of underlying geometric principles. The methods used to attack
many of the earlier problems relied heavily on entropy and covering properties.
Recently a major old conjecture on this subject, the Duality of Entropy
Conjecture, started to ``crack'' and we hope for a major breakthrough in
this direction.
Over the last decade, research in Isometric Convex Geometry has
begun to make connections with more and more areas of mathematics. The relations
of convexity to functional analysis, probability and combinatorics are emphasized
by the project and will be promoted further by it. One of the main objectives
of the project within convex geometry, is the continued study of the approximation
of convex bodies by polytopes. The topic has been enormously influenced
by random methods as shown by the recent discoveries of several members
of the net that the rates of random approximation and best approximation
are essentially the same. The objectives here are the extension
to non-smooth convex bodies of the asymptotically optimal formulas for the
degree of approximation which are known for smooth bodies, the expansion
of asymptotic formulas in the case of best approximation and the construction
of efficient algorithms for performing approximation.
Classical geometric inequalities such as the Brunn-Minkowski inequality have strong links with another main subject of the program: Isoperimetric Principles in Geometry and Probability. The most challenging questions in this direction concern stability results for geometric inequalities, which lead to better understanding of these inequalities, sharper versions and dramatic new applications.
The Asymptotic Combinatorics group has several long term goals in
combinatorics and theoretical computer science. One of them is to understand
better the asymptotic behavior of graph theoretic parameters in various
models of random graphs, in particular, parameters related to the spectrum,
such as eigenvalues, the Lov\'asz theta-function and vector chromatic
number. The study of these parameters cuts across several mathematical disciplines
such as spectral theory, the theory of random matrices and the theory of
algorithmic complexity, where these parameters are widely used. Several
recent results obtained by the group include the determination of the asymptotic
value of the choice
number in random graphs (Krivelevich) and random bipartite graphs
(Alon and Krivelevich) and the concentration of eigenvalues
of random symmetric matrices and its algorithmic applications (Alon,
Krivelevich and Vu). It is to be expected that there will be further
important progress in these areas.
Pseudo-random graphs can be informally defined as graphs whose properties resemble those of truly random graphs of the same density. The group plans to study pseudo-random graphs, and to find new constructions of them. Again there has been important recent work in this area: new constructions of geometric expanders have applications in computer simulation as well as providing concrete models of randomness.
The third thread of asymptotic combinatorics is Ramsey Theory. There are some exciting new bounds on Ramsey numbers recently provided by members of the group while Gowers has identified the possibility of finding very much more effective methods in the direction of Szemerédi's Theorem and its higher-dimensional generalisations.
The area of Randomised Computation and Complexity covers applications
of methods from probability theory and convex geometry to the design and
analysis of algorithms.
A benchmark problem has been that of computing the volume of high-dimensional
convex bodies: there has been enormous progress, but the task is still not
finished. Recent advances (many by project members) have opened up new possibilities,
such as the use of simulated annealing techniques and the applications of
more sophisticated expansion measures. Other important problems concern
the computation of geometric invariants such as diameter, center of gravity
and inertial ellipsoid that capture more detailed information than the volume.
A difficult and largely open area is to obtain lower bounds on the complexity of (randomised) volume computation and other algorithmic tasks. At this time, only essentially trivial lower bounds are known, and any progress in the direction (for example, a nonlinear lower bound on the minimum number of oracle calls that allow a randomized approximation of the volume) would be very significant.
The Mathematical Physics topics within the project fall into three
main areas. Universality is a crucial concept in the theory of eigenvalue
distribution of large random matrices, and refers to the appearance of common
patterns in asymptotic distribution of eigenvalues, that comprise a system
of strongly
dependent random variables. The group plans to find new approaches to the
universality of the local regime (for both the bulk of the spectrum and
its edges), valid under less stringent conditions and applicable to a wider
class of random matrix ensembles (e.g. orthogonally invariant ones) and
new
limiting probability laws for linear eigenvalue statistics, that will replace
the central limit theorem in the case where the support of the limiting
eigenvalue counting function consists of several intervals. The work will
involve new techniques based on the analysis of systems of functional equations,
asymptotic study of new classes of orthogonal polynomials, abstract Markov
operators and related techniques of spectral, logarithmic, and classical
Sobolev inequalities.
Within the statistical mechanics of disordered systems one of the most
challenging problems is to obtain an explicit form of the most relevant
physical quantities (such as free energy and correlation functions) for
the principal mean field models. Advances in this direction will follow
from further development
of the rigorous cavity method, proposed and successfully studied by the
Kharkov and Paris teams, combined with certain convexity considerations,
that proved to be efficient in recent progress in the field due to Guerra,
Talagrand and Shcherbina and Tirozzi. Some new models
in theoretical neurobiology, known as the ``integrate and fire'' mean field
models will be studied by means of the theory of stochastic differential
equations and Markov processes.
Studies of spectral and evolution properties of PDE's will be based first
of all on the recent considerable progress in the analysis of convexity
properties of eigenvalues for boundary value problems defined by elliptic
PDE's. In particular, a new proof providing equality conditions, of the
Brunn-Minkowski inequality for the first eigenvalue of the Laplacian, was
given by members of the Italian team. One of the main tasks will be to find
natural assumptions
on a variational set functional, which ensure that it obeys a Brunn-Minkowski
type inequality and unifying results that imply as special cases the existing
inequalities. It is also planned to study geometric and analytic properties
of global attractors for infinite dimensional dissipative dynamical systems
generated
by initial boundary-value problems for nonlinear partial differential equations.
The focus will be on mixed systems, important in the physics of multi-component
and multi-layer structures and in climate and weather modelling, and on
the cases where global attractors have no regular structure. It is
also planned to find new finite-dimensional approximate inertial manifolds
for deterministic and stochastic retarded equations, where infinitely many
additional degrees of freedom appear in comparison with the non-retarded
case.
In the area of Isoperimetric principles it will be important to investigate further the interplay between geometric inequalities, mass transportation and probabilistic and semigroup tools. A new avenue in this direction concerns the (Riemannian) geometry of the space of probability distributions equipped with the Wasserstein distance: it is becoming clearer that there is a connection between the curvature of the space and the displacement convexity of entropy functionals. It is to be expected that the study of convergence to equilibrium of fast diffusions, in the entropy or Wasserstein distances, via functional transportation and Sobolev inequalities will be a fruitful source of interaction with the PDE community. Thanks to the work of project members in the last three years, it has become possible for the first time to attempt a serious study of entropy growth for discrete semi-groups: something which was previously only possible for the extremely restricted class of continuous semi-groups.