Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We present the following theorem: for fixed d, the generating function of the projection of the set of integer points in a d-dimensional polytope is computable in polynomial time. We can use this theorem to find the generating functions for some interesting sets of lattice points, such as minimal Hilbert bases, test sets for integer programming, and the set of all numbers representable as a nonnegative integer combination of given coprime integers. As a consequence, we can answer related questions (for example, what is the cardinality of these sets?) quickly.