UC Berkeley

Linear and semidefinite programs are fundamental algorithmic tools, often providing conjecturally

optimal results for a variety of combinatorial optimization problems. Thus, a natural

question 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 dissertation, I will give two results of this flavor. First, I will show that any linear

programming relaxation for refuting random instances of constraint satisfaction problems

(e.g. k-SAT) requires super-polynomial size. This theorem can be understood as evidence

that refuting CSPs is hard, since it rules out a broad class of algorithms. Second, I will

show that any symmetric semidefinite programming relaxation for the matching problem

in general graphs requires exponential size. Since there is a polynomial time algorithm for

the matching problem, this result provides an example of the limitations of semidefinite

programming relaxations.