A threshold for online balancing of sparse i.i.d. vectors

2025/09/02 by Altschuler, Dylan J., Tikhomirov, Konstantin
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2509.02432

Abstract

Consider the task of online vector balancing for stochastic arrivals (X_i)_{i ∈ [T]}, where the time horizon satisfies T = Θ(n), and the X_i are i.i.d uniform d--sparse n--dimensional binary vectors, with 2≤ d ≤ (loglog n)²/logloglog n. We show that for this range of parameters, every online algorithm incurs discrepancy at least Ω(log log n), and there is an efficient algorithm which achieves a matching discrepancy bound of O(loglog n) w.h.p. This establishes an asymptotic gap, both existential and algorithmic, between the online and offline versions of the average--case Beck--Fiala problem. Strikingly, the optimal online discrepancy in the considered setting is order log log n, independent of d and the norms of the vectors (X_i)_i. Our assumptions on d are nearly optimal, as this independence ceases when d=ω((loglog n)²).

Citations

• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
• An Improved Bound for the Beck-Fiala Conjecture
• Optimal Online Discrepancy Minimization
• Distribution of the threshold for the symmetric perceptron
• Critical Window of The Symmetric Perceptron
• Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
• Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
• Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
• Frozen 1-RSB structure of the symmetric Ising perceptron
• The Discrepancy of Random Rectangular Matrices
• Online Carpooling using Expander Decompositions
• Discrepancy Minimization via a Self-Balancing Walk
• Online Vector Balancing and Geometric Discrepancy
• Balancing Covariates in Randomized Experiments with the Gram-Schmidt Walk Design
• On-Line Balancing of Random Inputs
• On the discrepancy of random low degree set systems
• A Logarithmic Additive Integrality Gap for Bin Packing

Related

• Online Discrepancy Minimization for Stochastic Arrivals
• Online Vector Balancing and Geometric Discrepancy
• Online Discrepancy Minimization via Persistent Self-Balancing Walks
• Discrepancy Minimization via a Self-Balancing Walk
• Online Beck--Fiala Down to Logarithmic Sparsity