Guest Talk: Thomas Rothvoss: Discrepancy Theory: Algorithms and Applications

Thursday, March 12, 2020, 11:00am

Location: RWTH Aachen University, SeMath, Pontdriesch 14-16, Room 008

Speaker: Thomas Rothvoss

Thomas Rothvoss is a very famous researcher in the area of optimization and theoretical computer science. Lately he awarded the Fulkerson Prize for "The Matching Polytope has Exponential Extension Complexity."

An exciting line of work, starting with Bansal’s seminal paper provides algorithms to find partial colorings in polytopes and more generally in large enough convex sets. The original motivation comes from discrepancy theory where the goal is to bi-color a given set of sets as evenly as possible. For example, this enables a constructive solution to Spencer’s “6-standard deviations suffice” Theorem. We show a surprising simple deterministic algorithm to find partial colorings in a polytope. Moreover we show how discrepancy theory can be used to obtain linear size spectral spartifiers in a graph, matching the result of Batson, Spielman and Srivastava. In particular such sparsifiers imply that in any undirected graph one can select a linear size set of edges with weights so that every cut is preserved up to a (1 + ε) factor.

This is joint work with Avi Levy, Harish Ramadas, and Victor Reis.