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.