Seminars & Colloquia Calendar

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.