Complexity in Geometric Combinatorics

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

The project aims at developing geometric methods to solve a variety of algorithmic problems regarding various combinatorial structures. The problems include enumeration of lattice points in certain sets (such as sets defined by formulas of Presburger arithmetic), asymptotic counting of combinatorial structures of a given 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 methods from 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 longer smooth but discrete. The project aims at developing efficient computational methods for some previously intractable problems dealing with exact or approximate enumeration in very large sets and finding maximum (minimum) of functions defined on large sets. Many of the considered problems are of interest to statistics, physics and optimization.