ECCC-Report TR16-079https://eccc.weizmann.ac.il/report/2016/079Comments and Revisions published for TR16-079en-usTue, 17 May 2016 22:12:26 +0300
Paper TR16-079
| Sum-of-squares hierarchy lower bounds for symmetric formulations |
Adam Kurpisz,
Samuli Lepp\"anen,
Monaldo Mastrolilli
https://eccc.weizmann.ac.il/report/2016/079We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of ``well-behaved'' univariate polynomial inequalities.
We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the \textsc{Min-Knapsack} linear program strengthened with cover inequalities. Tue, 17 May 2016 22:12:26 +0300https://eccc.weizmann.ac.il/report/2016/079