Return to Colloquia & Seminar listing
Algorithms for Discrepancy Minimization
Mathematics of Data & 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.