Is the Algorithmic Kadison-Singer Problem Hard?

Abstract

We study the following ${\mathsf{KS}}_2(c)$ problem: let $c\in {\mathbb{R}}^{+}$ be some constant, and $v_1,\dots ,v_m\in {\mathbb{R}}^d$ be vectors such that $\Vert v_i{\Vert }^2\le \alpha$ for any $i\in [m]$ and ${\sum }_{i=1}^m⟨v_i,x{⟩}^2=1$ for any $x\in {\mathbb{R}}^d$ with $\Vert x\Vert =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 $\Vert x\Vert =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 $\epsilon$ 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.