Nie jesteś zalogowany |
Discrepancy and Optimization
- Prelegent(ci)
- Adrian Vladu
- Afiliacja
- Boston University
- Termin
- 17 stycznia 2019 12:15
- Pokój
- p. 5870
- Seminarium
- Seminarium "Algorytmika"
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.
