Seminar

The structure of integer points in polytopes is of interest both in Combinatorics and Integer Programming.  The works of Lenstra (1983) and Barvinok (1993) showed that the decision and counting problems can be resolved in polynomial time when the polytope is in of bounded dimension.  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.)   In a series of papers this year we show that there are sharp limits to how far this approach can be advanced.  Notably, we prove that satisfiability of short formulas with three quantifiers is NP-complete.



In the first part 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 part 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.  It will also be somewhat entertaining with at least oneunexpected plot twist midway through the story.