Dissertation Talk: Extended Formulation Lower Bounds for Combinatorial Optimization

Presentation: Dissertation Talk: CS | May 8 | 3-4 p.m. | 373 Soda Hall

 Jonah Brown-Cohen

 Electrical Engineering and Computer Sciences (EECS)

Linear and semidefinite programs are fundamental algorithmic tools, often providing conjecturally optimal results for a variety of combinatorial optimization problems. Thus, a natural problem is to understand the limitations of linear and semidefinite programming relaxations. In particular, the goal is to prove unconditional lower bounds on the size of any linear or semidefinite programming relaxation for a given problem.

In this talk, I will give two results of this flavor. First, I will show that any linear programming relaxation for refuting random instances of 3-SAT requires super-polynomial size. Second, I will show that any symmetric semidefinite programming relaxation for the matching problem in general graphs requires exponential size.