Vector Balancing in Polynomial Time

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 $\mathrm{\parallel }A\epsilon {\mathrm{\parallel }}_{\mathrm{\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))$.