LFCS Seminar: Wednesday, 29 October: Daniel Spielman

Title: Algorithmic Discrepancy Theory

Abstract

We survey algorithms that have been used to effectively realize the
promises of discrepancy theory, including Beck and Fiala's technique for
minimizing Euclidean discrepancy, algorithmic versions of Spencer's
theorem, and the Gram-Schmidt Walk of Bansal, Dadush, Garg, and Lovett. We
will finish with some conjectures and open problems.

Bio:
Dan Spielman is the Sterling Professor of Computer Science, and Professor of Mathematics and Statistics, at Yale University. Spielman's wide-ranging research spans the design and analysis of algorithms, spectral graph theory, numerical linear algebra, coding theory, linear programming, statistics and data science. He has received numerous awards for groundbreaking contributions in many of these areas, including the Goedel Prize (twice, both in 2008 and 2015), the Fulkerson Prize (2009), the Nevanlinna Prize (2010), the Polya Prize (2014), the Held Prize (2021), and the Breakthrough Prize in Mathematics (2023).