Site map
Network structure

Network structure

Great Britain


Tel Aviv
Pierre et Marie Curie
Ecole Polytechnique
Rényi Institute

Warsaw Zaragoza
I. per le Applicazioni del Calcolo
Uni. ``Cattolica'',Milan
Polytechnic Univ.,Milan
University of Trieste
Nice Sofia-Antipolis
Tel Aviv
Weizmann Institute
Technion (Haifa)
Haifa University
Institute for Low Temperature
Kharkov State University

Research topic

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.