论文标题
算法Kadison-Singer问题是否严重？
Is the Algorithmic Kadison-Singer Problem Hard?
论文作者
论文摘要
我们研究以下$ \ Mathsf {ks} _2（c）$问题：让$ c \ in \ mathbb {r}^+$有些常数，而$ v_1，\ ldots，v_m \ in \ mathbb {r}^d $是$ \ | v_ | $ \ sum_ {i = 1}^m \ langle v_i，x \ rangle^2 = 1 $ in \ in \ mathbb {r}^d $，with $ x \ with $ \ | x \ | = 1 $。 $ \ mathsf {ks} _2（c）$问题要求找到一些$ s \ subset [m] $，以使其适用于所有$ x \ in \ mathbb {r}^d $，with $ \ | x \ | = 1美元\ leq c \ cdot \sqrtα，\]或报告否，如果不存在这样的$ s $。根据Marcus等人的工作。和weaver，$ \ mathsf {ks} _2（c）$问题可以看作是带有参数$ c \ in \ mathbb {r}^+$的算法的kadison-singer问题。 我们的第一个结果是一种随机算法，对于$ \ mathsf {ks} _2（c）$问题的单方面错误，以至于（1）我们的算法找到有效的集合$ s \ subset [m] $，概率至少$ 1-2/d，如果存在这样的$ s $，或者（2）不存在$ 1 $ $ 1 $ 1 $ 1 $ 1 $ 1 $ 1 $。该算法具有运行时间\ [o \ left（\ binom {m} {n} \ cdot \ cdot \ mathrm {poly}（m，d）（m，d）\ right）〜\ mbox { \ log \ left（\ frac {1} {c \sqrtα} \ right）\ right），\ right），其中$ε$是控制算法错误的参数。这是Kadison-Singer问题的第一种算法，该算法是$ M $的运行时间，尽管对$ D $具有指数依赖性。此外，它表明算法Kadison-Singer问题更容易在低维度中解决。 我们的第二个结果是$ \ Mathsf {ks} _2（c）$问题的计算复杂性。我们表明，$ \ Mathsf {ks} _2（1/（4 \ sqrt {2}））$问题是$ \ Mathsf {fnp} $ - 对于$ d $的一般值而言，很难求解$ \ Mathsf {ks} $ \ mathsf {nae \ mbox { - } 3SAT} $问题。
We study the following $\mathsf{KS}_2(c)$ problem: let $c \in\mathbb{R}^+$ be some constant, and $v_1,\ldots, v_m\in\mathbb{R}^d$ be vectors such that $\|v_i\|^2\leq α$ for any $i\in[m]$ and $\sum_{i=1}^m \langle v_i, x\rangle^2 =1$ for any $x\in\mathbb{R}^d$ with $\|x\|=1$. The $\mathsf{KS}_2(c)$ problem asks to find some $S\subset [m]$, such that it holds for all $x \in \mathbb{R}^d$ with $\|x\| = 1$ that \[ \left|\sum_{i \in S} \langle v_i, x\rangle^2 - \frac{1}{2}\right| \leq c\cdot\sqrtα,\] or report no if such $S$ doesn't exist. Based on the work of Marcus et al. and Weaver, the $\mathsf{KS}_2(c)$ problem can be seen as the algorithmic Kadison-Singer problem with parameter $c\in\mathbb{R}^+$. Our first result is a randomised algorithm with one-sided error for the $\mathsf{KS}_2(c)$ problem such that (1) our algorithm finds a valid set $S \subset [m]$ with probability at least $1-2/d$, if such $S$ exists, or (2) reports no with probability $1$, if no valid sets exist. The algorithm has running time \[ O\left(\binom{m}{n}\cdot \mathrm{poly}(m, d)\right)~\mbox{ for }~n = O\left(\frac{d}{ε^2} \log(d) \log\left(\frac{1}{c\sqrtα}\right)\right), \] where $ε$ is a parameter which controls the error of the algorithm. This presents the first algorithm for the Kadison-Singer problem whose running time is quasi-polynomial in $m$, although having exponential dependency on $d$. Moreover, it shows that the algorithmic Kadison-Singer problem is easier to solve in low dimensions. Our second result is on the computational complexity of the $\mathsf{KS}_2(c)$ problem. We show that the $\mathsf{KS}_2(1/(4\sqrt{2}))$ problem is $\mathsf{FNP}$-hard for general values of $d$, and solving the $\mathsf{KS}_2(1/(4\sqrt{2}))$ problem is as hard as solving the $\mathsf{NAE\mbox{-}3SAT}$ problem.
