论文标题
Weaver差异问题的硬度结果
Hardness Results for Weaver's Discrepancy Problem
论文作者
论文摘要
Marcus, Spielman and Srivastava (Annals of Mathematics 2014) solved the Kadison--Singer Problem by proving a strong form of Weaver's conjecture: they showed that for all $α> 0$ and all lists of vectors of norm at most $\sqrtα$ whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most $\sqrt{8 α} +2α。$ $我们证明，区分这样的向量列表是np-hard，其中有一个签名的总和等于每个签名总和具有至少$κ\sqrtα$的零矩阵的零矩阵，因为它是一个绝对常数的$κ> 0，因此，它是一个不变的。 对于$α= 1/4 $，我们证明，区分是否有一个签名总和等于零矩阵与每个签名总和具有运算符规范至少$ 1/4 $的情况是NP-HARD。
Marcus, Spielman and Srivastava (Annals of Mathematics 2014) solved the Kadison--Singer Problem by proving a strong form of Weaver's conjecture: they showed that for all $α> 0$ and all lists of vectors of norm at most $\sqrtα$ whose outer products sum to the identity, there exists a signed sum of those outer products with operator norm at most $\sqrt{8 α} + 2 α.$ We prove that it is NP-hard to distinguish such a list of vectors for which there is a signed sum that equals the zero matrix from those in which every signed sum has operator norm at least $κ\sqrtα$, for some absolute constant $κ> 0.$ Thus, it is NP-hard to construct a signing that is a constant factor better than that guaranteed to exist. For $α= 1/4$, we prove that it is NP-hard to distinguish whether there is a signed sum that equals the zero matrix from the case in which every signed sum has operator norm at least $1/4$.
