Title:  Constructive Algorithms for Discrepancy Minimization


Speaker: Nikhil Bansal, IBM 


Abstract: 

The problem of finding a minimum discrepancy coloring is the following:
Given n elements and a collection of sets S1,...,Sm, color the elements red and blue such that each
set is colored as evenly as possible. While several techniques have been developed to show
the existence of good colorings, obtaining such colorings algorithmically has been a long standing question.


In this talk, we will describe the first algorithmic results for the problem that essentially
match the known existential guarantees. Among other results, we show how to efficiently
construct an O(n^{1/2}) discrepancy coloring when m = O(n). 
This matches the celebrated "six standard deviations suffice" result
of Spencer up to constant factors.