Oct 11, 2016, 4pm
SAV 131
Harishchandra Ramadas, Department of Mathematics, University of Washington

Given a collection of n items and n subsets of this collection, we want to color each object either red or blue so that in every subset, the number of red items is close to the number of blue items. In 1985, Spencer showed that there exists a coloring so that the “discrepancy” of each subset — the difference between the number of red and blue items — is at most sqrt(n). We present a deterministic algorithm based on the multiplicative weights update method to find such a coloring in polynomial time.

Based on joint work with Avi Levy and Thomas Rothvoss. No background will be assumed.