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.