Vector Balancing in Polynomial Time

Abstract

We present a spectral signing algorithm solving the Komlós problem with a constant discrepancy in polynomial time. Given a matrix $A\in {\mathbb{R}}^{m\times n}$ whose columns have Euclidean norm at most $1$, the algorithm finds a vector $\epsilon \in \{-1,1{\}}^n$ satisfying $\Vert A\epsilon {\Vert }_{\infty }\le C$, where $C$ is an absolute constant. By minimizing a cubic spectral potential, our spectral signing algorithm updates the fractional coloring toward Boolean signs with time complexity $O((m{n}^9+n^{10})\log (2+m+n))$.

20 pages, no figures