Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 03/04: Yang P. Liu

David Wajc wajc at stanford.edu
Mon Mar 1 11:20:01 PST 2021


Hi all,

This week's theory lunch will take place Thursday at noon (PDT), at our
gather space:
https://gather.town/app/lR6jRBPK44nZ7V68/StanfordTheory (*password:*
 SongComplexity).
Yang will tell us about *Discrepancy Minimization via a Self-Balancing Walk*

*Abstract:*




*We study discrepancy minimization for vectors in 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 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.Cheers,DavidPSPro tip: To join the talk (at 12:30):(1) go to the
lecture hall, (2) grab a seat, and (3) press X to join the zoom lecture*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210301/a5b449a1/attachment-0001.html>


More information about the theory-seminar mailing list