# Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

### Algorithms for Discrepancy Minimization

**Mathematics of Data and Decisions**

Speaker: | Thomas Rothvoss, U Washington |

Related Webpage: | https://sites.math.washington.edu/~rothvoss/ |

Location: | 1147 MSB |

Start time: | Tue, Mar 5 2019, 4:10PM |

Abstract: A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. We continue this exciting line of research and present two new algorithms: (1) We present a deterministic polynomial time algorithm for finding colorings in the Lovett-Meka setting. The algorithm is based on the Multiplicative Weight Update Method. (2) It was known non-constructively that any symmetric convex set K with measure at least exp(-n/500) must contain a partial coloring, which is a point in [-1,1]^n with Omega(n) coordinates in {-1,+1}. We prove that a surprisingly simple algorithm can find such partial colorings.

This is joint work with Avi Levy and Harish Ramadas.