The threshold for online balancing of i.i.d. binary vectors

Dylan J. Altschuler, Konstantin Tikhomirov

Consider the task of online vector balancing for stochastic arrivals $X_1,\dots ,X_T$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1{\}}^n$.…