{"462381":{"#nid":"462381","#data":{"type":"event","title":"PhD Defense by Arefin Huq","body":[{"value":"\u003Cp\u003ETitle: The Complexity of Extended Formulations\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EArefin Huq\u003C\/p\u003E\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\u003Cp\u003ECollege of Computing\u003C\/p\u003E\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EDate: Monday, October 26, 2015\u003C\/p\u003E\u003Cp\u003ETime: 12pm - 3pm\u003C\/p\u003E\u003Cp\u003ELocation: Klaus 3100\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003ECommittee:\u003C\/p\u003E\u003Cp\u003EProf. Lance Fortnow (Co-advisor, SCS, Georgia Tech)\u003C\/p\u003E\u003Cp\u003EProf. Sebastian Pokutta (Co-advisor, ISyE, Georgia Tech)\u003C\/p\u003E\u003Cp\u003EProf. Greg Blekherman (Math, Georgia Tech)\u003C\/p\u003E\u003Cp\u003EProf. Dick Lipton (SCS, Georgia Tech)\u003C\/p\u003E\u003Cp\u003EProf. Santosh Vempala (SCS, Georgia Tech)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EExtended formulations are a powerful tool in combinatorial optimization that have received much attention in recent years. A central theme of current research is to understand the power and limits of formulations of varying types.\u003C\/p\u003E\u003Cp\u003EI will first present our result showing that the matching problem has no small symmetric semidefinite programming (SDP) formulation. Our work is the semidefinite analog of the result of Yannakakis showing that the matching problem does not have a small symmetric linear programming (LP) formulation.\u003C\/p\u003E\u003Cp\u003EI will then discuss formulations over the copositive and completely positive cones. While it is known that copositive programming is NP-hard, much is still not understood. I will propose two lines of research: one that would give a lower bound on the size of such formulations for many problems, and another that could lead to progress on an open question regarding the completely positive cone.\u003C\/p\u003E\u003Cp\u003E \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Complexity of Extended Formulations"}],"uid":"27707","created_gmt":"2015-10-26 10:39:54","changed_gmt":"2016-10-08 02:14:31","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-10-26T17:00:00-04:00","event_time_end":"2015-10-26T20:00:00-04:00","event_time_end_last":"2015-10-26T20:00:00-04:00","gmt_time_start":"2015-10-26 21:00:00","gmt_time_end":"2015-10-27 00:00:00","gmt_time_end_last":"2015-10-27 00:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}