List All Events

Download as iCal file

DIMACS Theory of Computing Seminar

Online Vector Balancing and Geometric Discrepancy

Sahil Singla (Princeton/IAS)

Location:  CoRE 301
Date & time: Wednesday, 20 November 2019 at 11:00AM - 12:00PM

Abstract:  We consider an online vector balancing question where T vectors, chosen from an arbitrary distribution over [-1,1]^n, arrive one-by-one and must be immediately given a {+, -} sign. The goal is to keep the discrepancy---the \(\ell_{\infty}\)-norm of any signed prefix-sum---as small as possible. A concrete example of this question is the online interval discrepancy problem where T points are sampled one-by-one uniformly in the unit interval [0,1], and the goal is to immediately color them {+,-} such that every sub-interval remains always nearly balanced. As random coloring incurs \(\Omega(T^{1/2})\) discrepancy, while the offline bounds are \(\Theta((n\log T)^{1/2})\) for vector balancing and \(1\) for interval balancing, a natural question is whether one can (nearly) match the offline bounds in the online setting for these problems. One must utilize the stochasticity as in the worst-case scenario it is known that discrepancy is \(\Omega(T^{1/2})\) for any online algorithm.