This award supports the research of Professor Alexandre Barvinok on the construction of algorithms for computational problems in combinatorics and algebra. The main goal is to find non-trivial upper bounds for the computational complexity of these problems by exploring the underlying algebraic structure. Three specific topics are being investigated. The first topic includes the applications of exponential sums to a wide range of computational problems. The second deals with applications of the representation theory of the symmetric group to hard problems in combinatorial optimization. The third topic involves quantifier elimination in integer programming, a specific unresolved question concerning integral points in polyhedra. The algorithms developed have potential practical applications to real world problems that reduce to hard enumeration. This research is in the general area of Combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.
