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...
Read More