Discrepancy Minimization via a Self-Balancing Walk

Combinatorics Seminar
Friday, October 9, 2020 - 3:00pm for 1 hour (actually 50 minutes)
https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke)
Yang P. Liu – Stanford University – https://yangpliu.github.io
Lutz Warnke

We study discrepancy minimization for vectors in R^n under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms for logarithmic bounds for the Komlós conjecture.

Based on joint work with Alweiss and Sawhney, see https://arxiv.org/abs/2006.14009