Advances in Vector Balancing

Seminar in Mathematics

In 1985, Spencer showed that for any v_1, ..., v_n in [-1, 1]^n one can find signs x_1, ..., x_n in {-1, 1} so that the signed sum x_1 v_1 + ... + x_n v_n has coordinates bounded by 6 * sqrt(n). Since then, several generalizations have been conjectured by changing the assumption on the input vectors, most of which remain open. I will discuss recent progress on two of them: when the vectors belong to the Euclidean ball, we obtain tight bounds on the online setting where vectors arrive one by one. When the vectors belong to a given zonotope, we obtain a generalization of Spencer's theorem up to a triple logarithm. Based on joint works with Rainie Bozzai, Janardhan Kulkarni and Thomas Rothvoss.