University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Counting vertices of integral polytopes defined by facets

## Counting vertices of integral polytopes defined by facetsAdd 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:Note that ex-directory lists are not shown. |
## Other listsMetallurgy & Materials – Tech Entrepreneurship Seminar Series Electromagnetic Communications and Sensing Research Seminar Series Beverley Glover## Other talksThe tragic destiny of Mileva Marić Einstein TBA Quantum Sensing in Space Life : it’s out there, but what and why ? TBA TBA |