The complexities of integer points in polytopes

09/19/2017 - 12:15pm
09/19/2017 - 1:10pm
Danny Nguyen (UCLA)

The structure of integer points in polytopes is of interest both in Combinatorics and Integer Programming. Given a polytope in fixed dimension, the works of Lenstra (1983) and Barvinok (1993) showed that finding and counting integer points can be solved in polynomial time. This led to a series of subsequent developments by Kannan, Barvinok, Woods and others, generalizing these results to various operations on polytopes (union, projection, etc.). An important generalization of these problems asks for satisfiability of formulas in Presburger arithmetic. We show that there are sharp limits on any positive results in the generalized setting. Notably, we prove that satisfiability of with three quantifiers in dimension 5 is NP-complete. In the first half of the talk we give a broad overview the subject. We state the results, explain the tools that were used, and how the new results fit the existing literature. In the second half of the talk, we will outline the proof of the main complexity result, which employs working with continued fractions and arithmetic progressions. The talk will be self contained and assume no prior knowledge of the subject.

Millikan 2099, Pomona College