Online Banaszczyk conjecture for online vector balancing
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Sinho Chewi, Patrik Gerber, Philippe Rigollet and Paxton Turner, “Gaussian discrepancy: a probabilistic relaxation of vector balancing”, arXiv:2109.08280 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.