Tight Hardness of the Non-commutative Grothendieck Problem
Tight Hardness of the Non-commutative Grothendieck Problem
复制标题
非交换格洛腾迪克问题的严格硬度
DOI：
10.4086/toc.2017.v013a015
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Rishi Saket
中科院分区：
文献类型：
--
作者：
J. Briët;O. Regev;Rishi Saket
我们证明，将非交换格罗滕迪克问题近似到大于二分之一的任何常数因子以内是NP难的，这与纳奥尔、雷格夫和维迪克（STOC'13）的算法的近似比相匹配。我们的证明使用了将有限维希尔伯特空间嵌入到赋予迹范数的矩阵空间中，其性质是标准基向量的像比没有大坐标的单位向量的像更长。
We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of finite-dimensional Hilbert spaces into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.