Online Discrepancy of Sparse Random Vectors over Long Horizons
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.34410
curl -X POST /api/v1/records/arxiv/2610.34410/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.34410/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'