@inproceedings{kulkarni2024optimal,
author = {Kulkarni, Janardhan (Jana) and Reis, Victor and Rothvoss, Thomas},
title = {Optimal online discrepancy minimization},
booktitle = {STOC'24},
year = {2024},
month = {June},
abstract = {We prove that there exists an online algorithm that for any sequence of vectors  with  arriving one at a time, decides random signs  so that for every  the prefix sum  is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums -subgaussian, and gives a  bound on the discrepancy  Our proof combines a generalization of Banaszczyk's prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching  strategy for an oblivious adversary.},
url = {http://approjects.co.za/?big=en-us/research/publication/optimal-online-discrepancy-minimization/},
pages = {1832-1840},
}