Return to Colloquia & Seminar listing
Online discrepancy minimization for sparse i.i.d. arrivals
Mathematics of Data & Decisions| Speaker: | Konstantin Tikhomirov, CMU |
| Related Webpage: | https://www.andrew.cmu.edu/user/ktikhomi/ |
| Location: | 1025 PDSB |
| Start time: | Tue, Oct 21 2025, 3:10PM |
Consider the problem of online discrepancy minimization in the average-case Back-Fiala setting, where T i.i.d. random vectors are uniformly distributed on the set of 0/1 vectors with exactly d ones. We show that for parameter d slowly growing with dimension n and in the regime where T is of order n, there is an online algorithm achieving discrepancy of order log log n, which is optimal. Strikingly, the resulting bound is independent of d, and is in sharp contrast with the task of discrepancy minimization in the offline setting, where the optimal discrepancy is known to be of order sqrt{d} for the considered model of randomness. Based on joint work with Dylan Altschuler, https://arxiv.org/abs/2509.02432
This talk will be held jointly with the Probability Seminar.