You are not logged in |
Discrepancy and Optimization
- Speaker(s)
- Adrian Vladu
- Affiliation
- Boston University
- Date
- Jan. 17, 2019, 12:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Algorithms
We consider the problem of minimizing the discrepancy of a set system. In 1985, Spencer proved that for m sets over a universe of n elements, one can always achieve a coloring with discrepancy O(sqrt(n log (m/n))), thus beating what could be achieved by a standard application of the Chernoff plus union bound. In 2010, Bansal finally made this result constructive, by providing an algorithm based on rounding a sequence of semidefinite programs; this was followed in 2012 by another constructive algorithm, based on a random walk inside a polytope, due to Lovett and Meka.
In this talk, I continue the line of constructive algorithms for discrepancy minimization. I will show that Spencer's result can be easily recovered by invoking a small set of tools from convex optimization. I will present a new deterministic polynomial time algorithm essentially based on Newton's method. No prior background on optimization will be assumed. Time permitting, I will discuss potential extensions of this approach to a few major open problems in discrepancy theory.
* This will be a 90 minutes long blackboard talk.
