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