文章基本信息

标题：Unique Games on the Hypercube
本地全文：下载
作者：Naman Agarwal ; Guy Kindler ; Alexandra Kolla 等
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2015
卷号：2015
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(Z_2)$. We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Games on the hypercube.