Counting vertices of integral polytopes defined by facets

Abstract

We present a number of complexity results concerning the problem of counting vertices of an integral polytope defined by a system of linear inequalities. The focus is on polytopes with small integer vertices, particularly 0/1 polytopes and half-integral polytopes.

15 pages. Minor edits, including a small change to the title. This version is accepted for publication in Discrete and Computational Geometry