  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 \alpha$ 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{\alpha},\] 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}{\epsilon^2} \log(d)
\log\left(\frac{1}{c\sqrt{\alpha}}\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.
