Title: Constructive Algorithms for Discrepancy Minimization
Speaker: Nikhil Bansal, IBM TJ Watson
Abstract: The minimum discrepancy problem is the following: Given a collection
of sets S1,...,Sm, color the elements red and blue such that each set is
colored as evenly as possible. While various techniques have been developed to
show the existence of good colorings, finding them efficiently has been a long
standing question.
In this talk, I will describe the first algorithmic results that essentially
match the known existential guarantees. Among other results, we show how to
efficiently construct an O(n^{1/2}) discrepancy coloring for m = O(n) sets,
matching the celebrated "six standard deviations suffice" result of Spencer.
Our main idea is to produce the coloring over time by defining a certain
correlated Brownian motion. The motion at each step is defined by the solution
to a semidefinite program, where this program itself is guided by the so-called
entropy method.