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.