(Fast) algorithms for discrepancy minimization

Given a set system S_1,...,S_n over the ground set [n], the minimum discrepancy problem seeks to find a 2-coloring of the elements of the ground set so that the discrepancy i.e. the maximum (over S_1,..., S_n) imbalance of colors in a set is minimized. In a breakthrough work, Bansal provided a polynomial time algorithm to find such a 2-coloring achieving discrepancy O(n^{1/2}), matching (up to a constant factor) a celebrated existential result of Spencer. In this talk, I will discuss some recent directions in algorithmic discrepancy focusing, in particular, on a near input-sparsity time algorithm for Spencer's theorem.  

Based on joint work with Ashwin Sah (MIT) and Mehtaab Sawhney (MIT).