Rounding Semidefinite Programming Hierarchies via Global Correlation
Rounding Semidefinite Programming Hierarchies via Global Correlation
复制标题
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
David Steurer
中科院分区：
文献类型：
--
作者：
B. Barak;P. Raghavendra;David Steurer
我们根据这些层次结构与输入图之间的连接，将半确定编程（SDP）层次结构的向量解决方案（SDP）层次结构进行圆形矢量解决方案展示了新的方法。我们通过提供新的基于SDP层次结构的新算法来证明我们方法的实用性，该算法通过2个变量的约束（2-CSP）来解决约束满意度问题。更具体地说，我们显示每2美元$ -CSP实例$ \ ins $，这是一种$ r $ $ $ $ $ $ $ $ $ $ $ rasserre sdp层次结构的舍入算法只要\ [r＆gt，k \ cdot \ stark _ {\ geq \ theta}（\ ins）/\ poly（\ e）\; \]其中$ k $是$ \ ins $，$ \ theta = \ poly（\ e/k）$的字母大小，$ \ rank _ {\ geq \ theta}（\ ins）$表示特征的数量$ \ ins $的约束图的归一化邻接矩阵中的值大于$ \ theta $。如果$ \ ins $是\唯一的游戏实例，则阈值$ \ theta $只是$ \ e $的多项式，并且独立于字母大小。同样，在这种情况下，我们可以对\ emph {every}实例的回合数进行非平凡的界限。特别是我们的结果产生了一种基于SDP层次结构的算法，该算法与最坏的情况下的Aurora，Barak和Steurer（Barak和Steurer（FOCS 2010）的最近子指数算法的性能相匹配，但在自然的实例上运行得更快，从而进一步限制了这种情况KHOT独特游戏猜想的一系列可能的硬实例。实际上，我们的算法需要小于$ n^{o（r）} $约束，由$ r^{th} $级别的lasserre层次结构级别，在某些情况下可以及时评估我们程序的$ r $回合$ 2^{o（r）} \ poly（n）$。
We show a new way to round vector solutions of semi definite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every $2$-CSP instance $\Ins$, a rounding algorithm for $r$ rounds of the Lasserre SDP hierarchy for $\Ins$ that obtains an integral solution which is at most $\e$ worse than the relaxation's value (normalized to lie in $[0,1]$), as long as\[ r >, k\cdot\rank_{\geq \theta}(\Ins)/\poly(\e) \;,\]where $k$ is the alphabet size of $\Ins$, $\theta=\poly(\e/k)$, and $\rank_{\geq \theta}(\Ins)$ denotes the number of eigen values larger than $\theta$ in the normalized adjacency matrix of the constraint graph of $\Ins$. In the case that $\Ins$ is a \unique games instance, the threshold $\theta$ is only a polynomial in $\e$, and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for \emph{every} instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent sub exponential algorithm of Aurora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the $n^{O(r)}$ constraints specified by the $r^{th}$ level of the Lasserre hierarchy, and in some cases $r$ rounds of our program can be evaluated in time$2^{O(r)}\poly(n)$.