**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.