Zusammenfassung
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 $n$-vertex
graphs are not the linear image of the feasible region of any SDP (i.e., any
spectrahedron) of dimension less than $2^n^c$, for some constant $c > 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)$ sum-of-squares relaxations. This result implies, for instance,
that no family of polynomial-size SDP relaxations can achieve better than a
7/8-approximation for MAX-3-SAT.
Nutzer