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.
Best Answer
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.)