Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization

David Gamarnik, Eren C. Kızıldağ, Will Perkins +1

For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This…