Extended Formulation Lower Bounds for Combinatorial Optimization
Jonah Brown-Cohen · eScholarship (California Digital Library) · 2018
Linear and semidefinite programs are fundamental algorithmic tools, often providing conjecturallyoptimal results for a variety of combinatorial optimization problems. Thus, a naturalquestion 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 orsemidefinite programming relaxation for a given problem.In this dissertation, I will give two results of this flavor. First, I will show that any linearprogramming relaxation for refuting random instances of constraint satisfaction problems(e.g. k-SAT) requires super-polynomial size. This theorem can be understood as evidencethat refuting CSPs is hard, since it rules out a broad class of algorithms. Second, I willshow that any symmetric semidefinite programming relaxation for the matching problemin general graphs requires exponential size. Since there is a polynomial time algorithm forthe matching problem, this result provides an example of the limitations of semidefiniteprogramming relaxations.