A threshold for online balancing of sparse i.i.d. vectors
Dylan J. Altschuler and Konstantin Tikhomirov · 2025
Read A threshold for online balancing of sparse i.i.d. vectors by Dylan J. Altschuler and Konstantin Tikhomirov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02432.txt.
Description
Dylan J. Altschuler and Konstantin Tikhomirov wrote a 2025 paper on online vector balancing. Random sparse vectors arrive one by one. Each one must get a sign at once, with no chance to revise it. The goal is to keep running totals small. Offline versions can see all vectors first.
For binary vectors with few ones, the authors prove a sharp threshold. Every online method is forced to accept some imbalance. That imbalance grows like the double logarithm of the dimension. An efficient method matches that bound with high probability. So the online cost is pinned down exactly. Oddly, the answer does not depend on sparsity in this range. It does not depend on vector norms either. The result splits online from offline performance for the average-case Beck-Fiala problem.
Catalog record
| CREATOR | Dylan J. Altschuler and Konstantin Tikhomirov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-02432