{"63384":{"#nid":"63384","#data":{"type":"event","title":"Rank Lower Bounds for Generic Cutting-Plane Proof Systems","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETITLE:\u003C\/strong\u003E\u0026nbsp; Rank Lower Bounds for Generic Cutting-Plane Proof Systems\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESPEAKER:\u0026nbsp; \u003C\/strong\u003ESebastian Pokutta - faculty candidate\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EABSTRACT:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe introduce a natural abstraction of cutting-plane proof systems, which subsumes well-known operators such as Gomory-Chv\u00e1tal, lift-and-project, Sherali-Adams, Lov\u00e1sz-Schrijver, and split cuts.  We exhibit a family of polytopes without integral points contained in the n-dimensional 0\/1-cube that has rank Omega(n\/ log n) for any proof system in our class.  In fact, we show that whenever a specific cutting-plane based proof system has (maximal) rank n\u003Cbr \/\u003Eon a particular family of instances, then any cutting-plane proof system in our class has rank Omega(n\/ log n) for this family.  We also construct a new cutting-plane proof system that has worst-case rank O(n\/ log n) for any polytope without integral points, implying that the new universal lower bound is virtually tight.\u003Cbr \/\u003E(joint work with Andreas S. Schulz)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cbr \/\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Rank Lower Bounds for Generic Cutting-Plane Proof Systems"}],"uid":"27187","created_gmt":"2011-01-05 11:51:32","changed_gmt":"2016-10-08 01:53:40","author":"Anita Race","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-02-01T10:00:00-05:00","event_time_end":"2011-02-01T11:00:00-05:00","event_time_end_last":"2011-02-01T11:00:00-05:00","gmt_time_start":"2011-02-01 15:00:00","gmt_time_end":"2011-02-01 16:00:00","gmt_time_end_last":"2011-02-01 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}