Towards computing the Grothendieck constant
Towards computing the Grothendieck constant
复制标题
计算格洛腾迪克常数
DOI：
10.1137/1.9781611973068.58
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
David Steurer
中科院分区：
文献类型：
--
作者：
P. Raghavendra;David Steurer
格罗滕迪克常数$KG$是满足如下条件的最小常数：对于任意的$d\in N$以及任意矩阵$A=(a_{ij})$，
\[
[等式]
\]
其中$B(d)$是$R^d$中的单位球。尽管人们做出了一些努力[15, 23]，常数$KG$的值仍然未知。格罗滕迪克常数$KG$恰好是$KM$，$N$-二次规划问题的一种自然半定规划松弛的整性间隙。这个问题的输入是一个矩阵$A=(a_{ij})$，目标是在$x_iy_j\in[-1,1]$的条件下最大化二次型$\sum_{ij}a_{ij}x_iy_j$。
在这项工作中，我们将[22]中的技术应用于$KM$，$N$-二次规划问题。通过一些标准但不平凡的修改，[22]中的归约得出了以下困难性结果：假设唯一博弈猜想[9]成立，要将$KM$，$N$-二次规划问题近似到比格罗滕迪克常数$KG$更好的任何因子都是NP难的。
通过改编在格罗滕迪克不等式证明中使用的“自举”论证，我们能够进行比[22]更严格的分析。通过这种仔细的分析，我们得到了以下新结果：
• 一种$KM$，$N$-二次规划的近似算法，它保证能实现任意接近格罗滕迪克常数$KG$的近似比（假设唯一博弈猜想成立时的最优近似比）。
• 我们表明格罗滕迪克常数$KG$可以在误差为$\eta$的范围内计算出来，计算时间仅取决于$\eta$。具体来说，对于每个$\eta$，我们制定一个明确的有限线性规划，其最优值与格罗滕迪克常数的误差在$\eta$以内。
我们还展示了高斯希尔伯特空间上的一个简单算子族，它保证包含格罗滕迪克不等式的紧实例。
The Grothendieck constant KG is the smallest constant such that for every d ∈ N and every matrix A = (aij),
[EQUATION]
where B(d) is the unit ball in Rd. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM, N-Quadratic Programming problem. The input to this problem is a matrix A = (aij) and the objective is to maximize the quadratic form Σij aijxiyj over xiyj ∈ [−1, 1].
In this work, we apply techniques from [22] to the KM, N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM, N-Quadratic Programming problem to any factor better than the Grothendieck constant KG.
By adapting a "bootstrapping" argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results:
• An approximation algorithm for KM, N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture).
• We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant.
We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.