REVIEW 1 cited by
On-Line Balancing of Random Inputs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We consider an online vector balancing game where vectors $v_t$, chosen uniformly at random in $\{-1,+1\}^n$, arrive over time and a sign $x_t \in \{-1,+1\}$ must be picked immediately upon the arrival of $v_t$. The goal is to minimize the $L^\infty$ norm of the signed sum $\sum_t x_t v_t$. We give an online strategy for picking the signs $x_t$ that has value $O(n^{1/2})$ with high probability. Up to constants, this is the best possible even when the vectors are given in advance.
Forward citations
Cited by 1 Pith paper
-
Online Beck--Fiala Down to Logarithmic Sparsity
A new online random-walk algorithm achieves O(√d) prefix discrepancy for d-sparse vectors whenever d ≥ log(T)(log log T)^{2+η}, proving Beck–Fiala in that regime and resolving the online Spencer conjecture.
Discussion (0). Continue with ORCID to comment.