On-Line Balancing of Random Inputs

2019/03/16 by Bansal, Nikhil, Spencer, Joel H. · 7 citations
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1903.06898

Abstract

We consider an online vector balancing game where vectors v_t, chosen uniformly at random in \-1,+1\ⁿ, arrive over time and a sign x_t ∈ \-1,+1\ must be picked immediately upon the arrival of v_t. The goal is to minimize the L^∞ norm of the signed 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.

Cited by

• Binary perceptron computational gap -- a parametric fl RDT view
• A threshold for online balancing of sparse i.i.d. vectors
• Polynomial-time sampling despite disorder chaos
• Thinning to improve two-sample discrepancy
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• Phase transition of descending phase retrieval algorithms
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron

Related

• Online Discrepancy Minimization for Stochastic Arrivals
• Optimal Online Discrepancy Minimization
• Online Vector Balancing and Geometric Discrepancy
• A threshold for online balancing of sparse i.i.d. vectors
• On-Line Difference Maximization