*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: The Complexity of Extended Formulations
Arefin Huq
School of Computer Science
College of Computing
Georgia Institute of Technology
Date: Monday, October 26, 2015
Time: 12pm - 3pm
Location: Klaus 3100
Committee:
Prof. Lance Fortnow (Co-advisor, SCS, Georgia Tech)
Prof. Sebastian Pokutta (Co-advisor, ISyE, Georgia Tech)
Prof. Greg Blekherman (Math, Georgia Tech)
Prof. Dick Lipton (SCS, Georgia Tech)
Prof. Santosh Vempala (SCS, Georgia Tech)
Abstract:
Extended 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.
I 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.
I 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.
