OpenAlex ·
Exact Universality of Online Discrepancy
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.00103
- Original
- Read it at the publisher
- Topics
Abstract
We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as $M/N\toα\in(0,\infty)$, the optimal value divided by $\sqrt N$ converges to a limit $R_α$ independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In particular, it determines the exact asymptotic optimum for Rademacher inputs. For every $κ>R_α$, we construct a randomized online algorithm whose final signed sum has $\ell^\infty$ norm at most $κ\sqrt N$ with high probability; for $κ
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Sharp edge-spectral supersaturation for odd cycles
On the Parameterized Complexity of Coloring Discovery
Are trees really just butterflies in disguise?
Subexponential Approximation of the Permanent in Deterministic Polynomial Time
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.