Is the Algorithmic Kadison-Singer Problem Hard?

Ben Jourdan, Peter Macgregor, He Sun

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\…