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.