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

Given v₁,…, vₘᵈ with \|vᵢ\|²= α for all i∈[m] as input and suppose ∑ᵢ₌₁ᵐ | u, vᵢ |² = 1 for every unit vector uᵈ, Weaver's discrepancy problem asks for a partition S₁, S₂ of $[m]$, such that ∑_i∈ Sⱼ | u, vᵢ |² ≤ 1 -θ for some universal constant θ, every unit vector uᵈ and every j∈\1,2\. We prove that this problem can be solved deterministically in polynomial time when m≥ 49 d².