vector balancing problem I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.

This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest possible proof strategies?
I have vectors $v_1, \ldots, v_k$ in ${\bf R}^n$. Each of them has euclidean length at most $.01$, and for every unit vector $u \in {\bf R}^n$ they satisfy
$$\sum_{i=1}^k |\langle u,v_i\rangle|^2 = 1.$$
Is it possible to find a set of indices $S \subset \{1, \ldots, k\}$ such that
$$.0001 < \sum_{i \in S} |\langle u,v_i\rangle|^2 < .9999$$
for every unit vector $u$? This will imply the same bounds when summing over the complement of $S$.
The $.01$ and $.0001$ aren't important; I just need the result for some positive $\delta$ and $\epsilon$. But they have to be independent of $k$ and $n$. (This may seem unlikely, until you try to construct a counterexample.)
The motivation is that this is a (very slightly simplified) equivalent version of the famous Kadison-Singer problem. A solution would have important consequences in operator theory, harmonic analysis, and C*-algebra. Many people have worked on this problem, but perhaps not in the above form, which I feel exposes the combinatorial difficulty which is the real root of the problem.
 A: This is mainly a comment. My first guess would be that if it is true, then a random subset of density $1/2$ works. A result in this direction is Lemma 3.2 in 
M. Rudelson, Contact points of convex bodies, Israel Journal of Mathematics, 1997, Volume 101, Number 1, Pages 93-124.
It says:

Lemma :Let $x_1,...,x_k$ be vectors in $\mathbb R^n$, $\varepsilon_1,...,\varepsilon_k$ be independent Bernoulli variables, taking values $1,-1$ with probability $1/2$. Then
  $${\mathbb E} \left\| \sum_{i=1}^k \varepsilon_i |x_i\rangle {\langle x_i} | \right\|\leq C \log(n) \sqrt{\log(k)} \max_i \|x_i\| \left\| \sum_{i=1}^k |x_i\rangle \langle x_i| \right\|^{1/2}$$
  for some absolute constant C.

In your case, this says that a random set of density $1/2$ solves the easier problem where $\delta$ may depend on $n$ and $k$. At the same time it proves much more, since there is even concentration around $1/2$. More precisely, if $ \sum_{i=1}^k |x_i\rangle \langle x_i| =1$ and $\|x_i\|< \delta$, then
$${\mathbb E} \left\|\frac12 - \sum_{i=1}^k \eta_i |x_i\rangle {\langle x_i} | \right\|\leq C/2 \log(n) \sqrt{\log(k)} \cdot \delta,$$
where $\eta_i$ are independent Bernoulli with values in $\{0,1\}$. 
Since $n \leq k \delta^2$ (looking at the trace), an easy calculation shows that $\delta$ only depends on $k$. At the same time, it seems to me that the problem is getting easier if $k$ is larger, but I cannot substantiate this claim. Remark 3.3 in the same paper shows that the inequality cannot be improved to become independent of $n$ and $k$. This somehow shows that choosing a random subset is too naive; at least when one studies the expected value of the norm as in the inequality above.
A: This paper contains a proposed solution to the problem. The acknowledgements suggest that MO might have facilitated the solution, should it be correct. (I'm speculating that Gil Kalai found out about Nik Weaver's formulation of the problem from this MO question.)
