CSAIL Event Calendar: Previous Series

Constructive Algorithms for Discrepancy Minimization

Speaker: Nikhil Bansal , IBM TJ Watson
Date: October 12 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT

The problem of finding the minimum discrepancy coloring 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 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.

See other events that are part of Theory Colloquium 2010/2011

See other events happening in October 2010