Complexity in Geometric Combinatorics

该项目旨在开发几何方法来解决各种组合结构的各种算法问题。这些问题包括某些集合（如由Presburger算术公式定义的集合）中点阵点的枚举，给定类型的组合结构（如拟阵中的基）的渐近计数，以及某些普遍凸体（如非负多元多项式的凸锥）的度量和组合性质的理解。提出的方法包括开发处理多元有理函数的计算效率技术，理解非常大的有限度量空间的性质，以及应用凸几何的方法。在组合学中，我们感兴趣的是处理有限的，尽管非常大的集合，经典的分析方法常常失败，因为主要对象不再是光滑的，而是离散的。该项目旨在开发有效的计算方法来解决一些以前难以解决的问题，这些问题处理非常大的集合中的精确或近似枚举，并找到在大集合中定义的函数的最大值（最小值）。许多被考虑的问题都是统计学、物理学和最优化感兴趣的。

The project aims at developing geometric methods to solve a variety of algorithmicproblems regarding various combinatorial structures. The problems includeenumeration of lattice points in certain sets (such as sets defined by formulas of Presburger arithmetic), asymptotic counting of combinatorial structures of agiven type (such as bases in matroids), and understanding metric and combinatorial properties of some universal convex bodies (such as the convex cone of non-negative multivariate polynomials). The proposed approaches include developing computationally efficient techniques of working with multivariate rational functions, understanding properties of very large finite metric spaces, and applying methodsfrom convex geometry.In combinatorics, we are interested in working with finite, although very large, sets,where methods of classical analysis often fail because the main objects are no longersmooth but discrete. The project aims at developing efficient computational methodsfor some previously intractable problems dealing with exact or approximateenumeration in very large sets and finding maximum (minimum) of functions definedon large sets. Many of the considered problems are of interest to statistics, physicsand optimization.