Lower bounds on the size of semidefinite programming relaxations

with James R. Lee, Prasad Raghavendra. STOC 2015.

PDF

Best Paper Award at STOC 2015

abstract

We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on nn-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than 2nδ2^{n^{\delta}}, for some constant δ>0\delta > 0. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-O(1)O(1) sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/87/8-approximation for MAX 3 SAT.

keywords

  • semidefinite programming
  • lower bounds
  • constraint satisfaction problems
  • sum-of-squares method
  • strong relaxations
  • quantum information
  • machine learning