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.