A threshold for online balancing of sparse i.i.d. vectors

Dylan J. Altschuler, Konstantin Tikhomirov

Consider the task of \textit{online} vector balancing for stochastic arrivals $(X_i{)}_{i\in [T]}$, where the time horizon satisfies $T=\Theta (n)$, and the $X_i$ are i.i.d uniform $d$-…