Complexity in Geometric Combinatorics

点击翻译按钮获取中文摘要

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.