ONLINE VECTOR BALANCING

Abstract: We study discrepancy minimization for vectors in $mb{R}^n$ in an online setting. The main result is a pair of nearly-linear time online algorithms which maintain logarithmic bounds for the Koml'{o}s~conjecture. The first algorithm is based on a high-dimensional comparison argument while the second is based on a discrete random walk on the real line with the Gaussian distribution as a stationary distribution. (Joint w/ Ryan Alweiss, Yang P. Liu, Ashwin Sah)

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar