Online Banaszczyk conjecture for online vector balancing
Let be a sequence of vectors with Euclidean norm at most . In the oblivious adversarial online setting, the algorithm receives at time and outputs a sign . Online Banaszczyk conjecture. There exists a randomized algorithm that, with high probability, achieves
This conjecture asks for an online analogue of Banaszczyk's discrepancy bound. The source attributes it to Alweiss, and presents it as an open conjecture concerning efficient online balancing against an oblivious adversary.
References
Primary source
Sinho Chewi, Patrik Gerber, Philippe Rigollet and Paxton Turner, “Gaussian discrepancy: a probabilistic relaxation of vector balancing”, arXiv:2109.08280 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.