ARC Colloquium 9/5/2023 11am in Petit 102A

Mark Jerrum (Queen Mary)

Title: Counting vertices of integral polytopes defined by facets

Abstract:  I'll address the computational complexity of counting vertices of an integral polytope defined by a system of linear inequalities.  The focus will be on polytopes with small integer vertices, particularly 0/1 and half-integral polytopes.  The geometric approach to combinatorial optimisation, as explored in Schrijver's 3-volume monograph, provides plentiful examples of these.  The complexity of exact counting is pretty well understood, so I'll concentrate on approximate counting with guaranteed error bounds.  The complexity landscape is only partially understood, but there appear to be natural examples that are neither in P nor NP-hard. 

This is joint work with Heng Guo (Edinburgh)