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

Abstract

Given $v_1,\dots ,v_m\in {\mathbb{C}}^d$ with $\Vert v_i{\Vert }^2=\hat{I}\pm$ for all $i\in [m]$ as input and suppose ${\sum }_{i=1}^m|⟨u,v_i⟩{|}^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}|⟨u,v_i⟩{|}^2\le 1-\hat{I}¸$ for some universal constant $\hat{I}¸$, 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$.