The aim of the project is to develop a new combinatorial and probabilistic approach to geometric functional analysis and its applications. Some of new major ideas are expected to come from the concept of the combinatorial dimension, which is a general form of the classical Vapnik-Chervonenkis dimension. Arising from logic, probability theory and computer science, the use of the combinatorial dimension looks very promising also in a wide range of areas including geometric functional analysis (finding nice sections of convex bodies), convex geometry (study of polytopes), discrete geometry (counting integer points and cells in sets) and extremal combinatorics. This new combinatorial and probabilistic method is aimed at one of the hardest problems in the theory of empirical processes - describe the classes of functions for which the Central Limit Theorem holds uniformly. New aspects of the celebrated concentration of measure phenomenon will also be studied by a combination of probabilistic and purely geometric ideas. This might give an insight into relationships between random and deterministic structures in geometric functional analysis, as well as a new view of local versus global asymptotic convex geometries. Probabilistic approach will also be developed for problems of finding nice submatrices of large matrices, which arise in functional and harmonic analysis as well as in computer science.
The project opens new connections between functional analysis, combinatorics, probability, convex geometry and applied mathematics. The celebrated "probabilistic method" along with deterministic combinatorial, geometric and analytic methods will merge into one machinery, which may expand our knowledge on the relationships between chaos and pattern that arise in a variety of high-dimensional structures in pure mathematics and in computer science. From the practical point of view, the results expected from this machinery include justification of algorithms in machine learning, development of algorithms for storage of large amounts of data and for data transmission (such as error correction codes).
