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

CREATORDylan J. Altschuler and Konstantin Tikhomirov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-02432

Browse the full library · About the Tower of Babel