Combinatorial and Probabilistic Approach to Geometric Functional Analysis and Applications

该项目的目的是发展一种新的组合和概率方法来进行几何泛函分析及其应用。一些新的主要概念有望来自组合维度的概念，组合维度是经典的Vapnik-Chervonenkis维度的一般形式。组合维度的使用源于逻辑、概率论和计算机科学，在包括几何泛函分析(寻找凸体的良好截面)、凸几何(研究多面体)、离散几何(计算集合中的整点和单元)和极端组合学等广泛领域中也看起来非常有前途。这种新的组合和概率方法是针对经验过程理论中最困难的问题之一--描述中心极限定理一致成立的函数类。这一著名的度量集中现象的新方面也将通过概率和纯几何思想的结合来研究。这可能会让我们深入了解几何泛函分析中随机结构和确定性结构之间的关系，以及对局部和全局渐近凸几何的新观点。还将发展概率方法来解决在泛函分析和调和分析以及计算机科学中出现的寻找大矩阵的好的子矩阵的问题。该项目打开了泛函分析、组合学、概率、凸几何和应用数学之间的新联系。新的“概率方法”与确定性的组合、几何和分析方法将合二为一，这可能会扩展我们对纯数学和计算机科学中各种高维结构中出现的混沌和模式之间的关系的认识。从实践的角度来看，这台机器的预期结果包括机器学习中的算法证明，为存储大量数据和数据传输(如纠错码)开发算法。

AbstractThe aim of the project is to develop a new combinatorial andprobabilistic approach to geometric functional analysis and itsapplications. Some of new major ideas are expected to come from theconcept of the combinatorial dimension, which is a general form of theclassical Vapnik-Chervonenkis dimension. Arising from logic, probabilitytheory and computer science, the use of the combinatorial dimensionlooks very promising also in a wide range of areas including geometricfunctional analysis (finding nice sections of convex bodies), convexgeometry (study of polytopes), discrete geometry (counting integerpoints and cells in sets) and extremal combinatorics. This newcombinatorial and probabilistic method is aimed at one of the hardestproblems in the theory of empirical processes - describe the classes offunctions for which the Central Limit Theorem holds uniformly. Newaspects of the celebrated concentration of measure phenomenon will alsobe studied by a combination of probabilistic and purely geometric ideas.This might give an insight into relationships between random anddeterministic structures in geometric functional analysis, as well as anew view of local versus global asymptotic convex geometries.Probabilistic approach will also be developed for problems of findingnice submatrices of large matrices, which arise in functional andharmonic analysis as well as in computer science.The project opens new connections between functional analysis,combinatorics, probability, convex geometry and applied mathematics. Thecelebrated "probabilistic method" along with deterministiccombinatorial, geometric and analytic methods will merge into onemachinery, which may expand our knowledge on therelationships between chaos and pattern that arise in a variety ofhigh-dimensional structures in pure mathematics and in computer science. From the practical point of view, the results expected from this machineryinclude justification of algorithms in machine learning, development ofalgorithms for storage of large amounts of data and for datatransmission (such as error correction codes).