Vector Balancing in Polynomial Time

Shengtao Guo; Ethan X. Fang; Junwei Lu

In the authors' words

We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time. Given a matrix $A \in R^{m \times n}$ whose columns have Euclidean norm at most $1$ , the algorithm finds a vector $ε \in {- 1, 1}^{n}$ satisfying $∥ A ε ∥_{\infty} \leq 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}) lo g (2 + m + n))$ .

Main resultThe abstract does not state a limitation.

Vector Balancing in Polynomial Time

In the authors' words

More on Algorithms & complexity that day

Smoothed Analysis of Inconsistent A*

Hardness of Online Directed Steiner Network

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Parameter-Free Triangle Counting