UC Davis Mathematics

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.