%0 Journal Article %1 lee2014lower %A Lee, James R. %A Raghavendra, Prasad %A Steurer, David %D 2014 %K bounds readings relaxation semidefinite-programming %T Lower bounds on the size of semidefinite programming relaxations %U http://arxiv.org/abs/1411.6317 %X 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.

@article{lee2014lower, 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 $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.}, added-at = {2020-01-02T15:49:49.000+0100}, author = {Lee, James R. and Raghavendra, Prasad and Steurer, David}, biburl = {https://www.bibsonomy.org/bibtex/2f4f234310251130ccbdd9d5528fd7367/kirk86}, description = {[1411.6317] Lower bounds on the size of semidefinite programming relaxations}, interhash = {62d8f98a3d01c137de140932ae6c99f4}, intrahash = {f4f234310251130ccbdd9d5528fd7367}, keywords = {bounds readings relaxation semidefinite-programming}, note = {cite arxiv:1411.6317}, timestamp = {2020-01-02T15:49:49.000+0100}, title = {Lower bounds on the size of semidefinite programming relaxations}, url = {http://arxiv.org/abs/1411.6317}, year = 2014 }