Title	Discrepancy Minimization via a Self-Balancing Walk
Creator	Alweiss, Ryan
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2020-09-30T08:04
Description	We study discrepancy minimization for vectors in $\mathbb{R}^n$ under various settings. The main result is the analysis of a new simple random process in multiple dimensions through a comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors for several problems in online vector balancing posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well as linear time algorithms of logarithmic bounds for the KomlÃ³s conjecture.
Extent	23.0 minutes
Subject	Mathematics; Convex and discrete geometry; Dynamical systems and ergodic theory; Discrete mathematics
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Princeton University
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2021-03-30
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0396416
URI	http://hdl.handle.net/2429/77663
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Graduate
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos