Counting vertices of integral polytopes defined by facets

Add to your list(s) Download to your calendar using vCal

• Mark Jerrum, London
• Thursday 10 November 2022, 15:00-16:00
• LTC.

If you have a question about this talk, please contact Johannes Carmesin.

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. No knowledge of complexity theory beyond P and NP will be assumed.

This is joint work with Heng Guo (Edinburgh)

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• LTC
• School of Mathematics events

Note that ex-directory lists are not shown.