Date & Time: Tuesday, February 23, 2016, 14:00-15:30
Venue: Ramanujan Hall
Title:Constructive discrepancy minimization of convex sets
Speaker: Srikanth Srinivasan, 16Mathematics Department, IIT Bombay
Abstract: We will see a recent result of Thomas Rothvoss, that gives a constructive proof of a classical theorem in combinatorial discrepancy theory due to Spencer. Roughly, the problem is to colour the elements of a finite universe U red and blue so that each of a collection C of subsets has as small a discrepancy between the number of red and blue elements in it. Spencer showed that when |U| = |C| = n, the discrepancy can be made as small as O(\sqrt{n}). For a long time, it remained an open problem to give a constructive proof of this theorem, until a solution was provided by Nikhil Bansal in 2010. An alternate proof of Spencer's theorem was provided by a result of Lovett and Meka in 2012, and this result is generalized in the work of Rothvoss from 2014, which I will describe.