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).