{"id":"arxiv/2610.34410","url":"https://arxiv.org/abs/2610.34410","tags":["cs.DS","cs.DM","math.CO","math.PR"],"score":0,"title":"Online Discrepancy of Sparse Random Vectors over Long Horizons","domain":"cs.DS","source":"arxiv","authors":["Nicola Wengiel"],"reviews":0,"subject":"cs.DS","summary":"We study online vector balancing for independent sparse random vectors: each arrival is supported on a uniformly random set of $s$ of the $n$ coordinates, with nonzero entries equal to one (binary model) or independent random signs (signed model), and an online algorithm must sign each vector upon arrival. The prefix discrepancy is the largest $\\ell_\\infty$-norm of the signed sums up to the horizon $T$, the terminal discrepancy that of the sum at time $T$. For binary inputs with $2\\le s\\le n/2$ and $T=Θ(n)$, Altschuler and Tikhomirov showed that both are of order $\\sqrt{s}+\\log\\log n$; they…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-25","reactions":{}}