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.