Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime

Given $v_1,\dots ,v_m\in {\mathbb{C}}^d$ with $\mathrm{\parallel }{v}_i{\mathrm{\parallel }}^2=\alpha$ for all $i\in [m]$ as input and suppose ${\sum }_{i=1}^m\mathrm{\mid }⟨u,v_i⟩{\mathrm{\mid }}^2=1$ for every unit vector $u\in {\mathbb{C}}^d$, Weaver’s discrepancy problem asks for a partition $S_1,S_2$ of $[m]$, such that ${\sum }_{i\in S_j}\mathrm{\mid }⟨u,v_i⟩{\mathrm{\mid }}^2\le 1-\theta$ for some universal constant $\theta$, every unit vector $u\in {\mathbb{C}}^d$ and every $j\in \{1,2\}$. We prove that this problem can be solved deterministically in polynomial time when $m\ge 49d^2$.