{"669411":{"#nid":"669411","#data":{"type":"event","title":"ARC Colloquium: Mark Jerrum (Queen Mary)","body":[{"value":"\u003Cp\u003EARC Colloquium 9\/5\/2023 11am in Petit 102A\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMark Jerrum (Queen Mary)\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETitle: Counting vertices of integral polytopes defined by facets\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u0026nbsp; I\u0027ll address the computational complexity of counting vertices of an integral polytope defined by a system of linear inequalities.\u0026nbsp; The focus will be on polytopes with small integer vertices, particularly 0\/1 and half-integral polytopes.\u0026nbsp; The geometric approach to combinatorial optimisation, as explored in Schrijver\u0027s 3-volume monograph, provides plentiful examples of these.\u0026nbsp; The complexity of exact counting is pretty well understood, so I\u0027ll concentrate on approximate counting with guaranteed error bounds.\u0026nbsp; The complexity landscape is only partially understood, but there appear to be natural examples that are neither in P nor NP-hard.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Heng Guo (Edinburgh)\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EARC Colloquium\u0026nbsp; 9\/5\/2023\u003C\/p\u003E\r\n\r\n\u003Cp\u003E11am, Petit 102\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMark Jerrum (Queen Mary)\u003Cbr \/\u003E\r\n\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Counting vertices of integral polytopes defined by facets"}],"uid":"36512","created_gmt":"2023-09-04 21:20:29","changed_gmt":"2023-09-04 21:30:55","author":"wperkins3","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-09-05T11:00:00-04:00","event_time_end":"2023-09-05T12:00:00-04:00","event_time_end_last":"2023-09-05T12:00:00-04:00","gmt_time_start":"2023-09-05 15:00:00","gmt_time_end":"2023-09-05 16:00:00","gmt_time_end_last":"2023-09-05 16:00:00","rrule":null,"timezone":"America\/New_York"},"location":"Petit 102A","extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}