Lifting sum-of-squares lower bounds: degree-2 to degree-4
Lifting sum-of-squares lower bounds: degree-2 to degree-4
复制标题
DOI：
10.1145/3357713.3384319
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Sidhanth Mohanty;P. Raghavendra;Jeff Xu
中科院分区：
文献类型：
--
作者：
Sidhanth Mohanty;P. Raghavendra;Jeff Xu
4阶平方和（SoS）SDP松弛是一种功能强大的算法，它可以捕获最知名的多项式时间算法，用于解决各种问题，包括MaxCut，Sparrandom Cut，所有MaxCSP和张量PCA。尽管是一个显式的算法，具有相对较低的计算复杂度，4度的SoS SDP的限制没有得到很好的理解。例如，现有的完整性缺口并不排除顶点覆盖的（2−）-算法或通过4度SoS SDP的MaxCut的（0.878+）-算法，其中每一个都将反驳臭名昭著的唯一游戏猜想。我们展示了一个明确的映射，从解决方案的程度2平方和SDP（Goemans-Williamson SDP）的解决方案的程度4平方和SDP放松布尔变量。通过这种映射，可以将2度SoS SDP松弛的下限提升到4度SoS SDP的相应下限。我们使用这种方法获得了随机d-正则图，统计物理学中的Sherington-Kirkpatrick模型和PSD Grothendieck问题上MaxCut的4度SoS SDP下界。我们的构造使用了对候选SDP向量进行伪校准的想法，而以前它只用于产生候选矩阵，其中一个将显示为PSD，使用了大量的技术工作。此外，我们开发了一种不同的技术来约束的频谱规范的图形矩阵中出现的背景下，SoS的SDP。该技术更简单，在许多情况下比跟踪方法产生更好的边界-这是唯一的技术。
The degree-4 Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, Sparsest Cut, all MaxCSPs and tensor PCA. Despite being an explicit algorithm with relatively low computational complexity, the limits of degree-4 SoS SDP are not well understood. For example, existing integrality gaps do not rule out a (2−)-algorithm for Vertex Cover or a (0.878+)-algorithm for MaxCut via degree-4 SoS SDPs, each of which would refute the notorious Unique Games Conjecture. We exhibit an explicit mapping from solutions for degree-2 Sum-of-Squares SDP (Goemans-Williamson SDP) to solutions for the degree-4 Sum-of-Squares SDP relaxation on boolean variables. By virtue of this mapping, one can lift lower bounds for degree-2 SoS SDP relaxation to corresponding lower bounds for degree-4 SoS SDPs. We use this approach to obtain degree-4 SoS SDP lower bounds for MaxCut on random d-regular graphs, Sherington-Kirkpatrick model from statistical physics and PSD Grothendieck problem. Our constructions use the idea of pseudocalibration towards candidate SDP vectors, while it was previously only used to produce the candidate matrix which one would show is PSD using much technical work. In addition, we develop a different technique to bound the spectral norms of graphical matrices that arise in the context of SoS SDPs. The technique is much simpler and yields better bounds in many cases than the trace method – which was the sole technique for this purpose.