Discrepancy minimization via a self-balancing walk
Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
Abstract
We study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process in high dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as a linear time algorithm for logarithmic bounds for the Komlós conjecture.
Topics & Concepts
LogarithmMinificationConjectureSimple (philosophy)MathematicsArgument (complex analysis)Computer scienceDiscrete mathematicsCombinatoricsMathematical optimizationBiochemistryPhilosophyMathematical analysisEpistemologyChemistryMathematical Approximation and IntegrationAnalytic Number Theory ResearchMarkov Chains and Monte Carlo Methods