Dear participants of the combinatorial doctoral seminar,
This Thursday starting at 9:50, Martin Böhm (me) will present a paper
Thomas Rothvoß: Constructive discrepancy minimization for convex sets
The topic: Combinatorial discrepancy deals with assigning {-1,+1} to the ground set of a set system so that each set in the set system is as balanced as possible. A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2).
Recent work of Bansal (2010) shows that using a random walk guided by an SDP solution, one can find such a coloring in polynomial time. This was improved by Lovett and Meka (2012), showing a nicer, more general algorithm that uses just a random walk. (Participants with good memory might remember Martin Balko's presentation of this result at our seminar in summer 2013/2014.)
This paper improves on Lovett and Meka and presents an extremely simple, even more general algorithm that finds such a coloring. The algorithm just generates a random variable and then uses the ellipsoid method. The analysis is very easy as well.
The talk should be self-contained.