The matching problem has no small symmetric SDP. Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., & Zink, D. arXiv:1504.00703 [cs], April, 2015. arXiv: 1504.00703![The matching problem has no small symmetric SDP [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper abstract bibtex Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo\\textbackslashss\ recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \$n{\textasciicircum}k\$. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.
@article{braun_matching_2015,
title = {The matching problem has no small symmetric {SDP}},
url = {http://arxiv.org/abs/1504.00703},
abstract = {Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo\{{\textbackslash}ss\} recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \$n{\textasciicircum}k\$. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.},
urldate = {2015-04-07TZ},
journal = {arXiv:1504.00703 [cs]},
author = {Braun, Gábor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Roy, Aurko and Weitz, Benjamin and Zink, Daniel},
month = apr,
year = {2015},
note = {arXiv: 1504.00703},
keywords = {68Q17, 68R10, Computer Science - Computational Complexity}
}
Downloads: 0
{"_id":"K9f9niBkY9FS9ZGwB","bibbaseid":"braun-browncohen-huq-pokutta-raghavendra-roy-weitz-zink-thematchingproblemhasnosmallsymmetricsdp-2015","downloads":0,"creationDate":"2015-12-18T06:38:09.584Z","title":"The matching problem has no small symmetric SDP","author_short":["Braun, G.","Brown-Cohen, J.","Huq, A.","Pokutta, S.","Raghavendra, P.","Roy, A.","Weitz, B.","Zink, D."],"year":2015,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"The matching problem has no small symmetric SDP","url":"http://arxiv.org/abs/1504.00703","abstract":"Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo\\\\textbackslashss\\ recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \\$n{\\textasciicircum}k\\$. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.","urldate":"2015-04-07TZ","journal":"arXiv:1504.00703 [cs]","author":[{"propositions":[],"lastnames":["Braun"],"firstnames":["Gábor"],"suffixes":[]},{"propositions":[],"lastnames":["Brown-Cohen"],"firstnames":["Jonah"],"suffixes":[]},{"propositions":[],"lastnames":["Huq"],"firstnames":["Arefin"],"suffixes":[]},{"propositions":[],"lastnames":["Pokutta"],"firstnames":["Sebastian"],"suffixes":[]},{"propositions":[],"lastnames":["Raghavendra"],"firstnames":["Prasad"],"suffixes":[]},{"propositions":[],"lastnames":["Roy"],"firstnames":["Aurko"],"suffixes":[]},{"propositions":[],"lastnames":["Weitz"],"firstnames":["Benjamin"],"suffixes":[]},{"propositions":[],"lastnames":["Zink"],"firstnames":["Daniel"],"suffixes":[]}],"month":"April","year":"2015","note":"arXiv: 1504.00703","keywords":"68Q17, 68R10, Computer Science - Computational Complexity","bibtex":"@article{braun_matching_2015,\n\ttitle = {The matching problem has no small symmetric {SDP}},\n\turl = {http://arxiv.org/abs/1504.00703},\n\tabstract = {Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo\\{{\\textbackslash}ss\\} recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem yields at least as good an approximation as any symmetric SDP relaxation of size \\$n{\\textasciicircum}k\\$. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours.},\n\turldate = {2015-04-07TZ},\n\tjournal = {arXiv:1504.00703 [cs]},\n\tauthor = {Braun, Gábor and Brown-Cohen, Jonah and Huq, Arefin and Pokutta, Sebastian and Raghavendra, Prasad and Roy, Aurko and Weitz, Benjamin and Zink, Daniel},\n\tmonth = apr,\n\tyear = {2015},\n\tnote = {arXiv: 1504.00703},\n\tkeywords = {68Q17, 68R10, Computer Science - Computational Complexity}\n}\n\n","author_short":["Braun, G.","Brown-Cohen, J.","Huq, A.","Pokutta, S.","Raghavendra, P.","Roy, A.","Weitz, B.","Zink, D."],"key":"braun_matching_2015","id":"braun_matching_2015","bibbaseid":"braun-browncohen-huq-pokutta-raghavendra-roy-weitz-zink-thematchingproblemhasnosmallsymmetricsdp-2015","role":"author","urls":{"Paper":"http://arxiv.org/abs/1504.00703"},"keyword":["68Q17","68R10","Computer Science - Computational Complexity"],"downloads":0,"html":""},"search_terms":["matching","problem","small","symmetric","sdp","braun","brown-cohen","huq","pokutta","raghavendra","roy","weitz","zink"],"keywords":["dblp","68q17","68r10","computer science - computational complexity"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}