Thomas Rothvoss works at the intersection of theoretical computer science and discrete mathematics at the University of Washington, where he holds a joint appointment as a professor in the Mathematics and Computer Science departments. Professor Rothvoss is well known for his many breakthroughs across the areas of approximation algorithms, extension complexity, discrepancy theory and integer programming. In particular, he has developed the best approximation algorithms for the Steiner tree and Bin packing problems, he has proved exponential lower bounds on the extension complexity of fundamental polytopes in combinatorial optimization, he has developed efficient algorithms for discrepancy minimization and spectral sparsification, and has designed faster algorithms for the integer programming problem. He has received multiple best paper awards and is the recipient of the 2018 Delbert Ray Fulkerson and the 2023 Gödel Prize for his work showing the exponential extension complexity of the matching polytope.
On Wednesday 14 May, Professor Rothvoss will give a CWI Distinguished Lecture relating his award-winning work on the integer programming problem (FOCS 2023 best paper award). He will give a historical overview of lattice-based approaches for solving the integer programming problem leading up to his recent work, where he gives the first major improvement in running time in over 30 years.
This lecture is part of a one month sabbatical visit at CWI (1 May through 6 June), which was made possible with support from CWI's visiting researcher program and the Networks & Optimization group.
The lecture will take place in the Turing Zaal from 4-5pm and will be followed by a reception in the foyer from 5-6:30pm with drinks and snacks.
Please register by Wednesday 7 May by filling out the form provided here: FORM LINK.
The talk title and abstract are given below.
Title: Integer programming from Lenstra to Kannan and Lovász and Beyond
Abstract:
Integer linear programming arguably is one of the most important work horses in discrete optimization. In this talk, we will describe the development of theoretical algorithms to solve IPs, starting with Lenstra's algorithm which can solve IPs in polynomial time if n is fixed. Then we focus on a lattice result by Kannan and Lovász [KL88] which inspired Dadush to design an algorithm that could solve integer programs in a dramatically faster time of (log n)^O(n) subject to a conjectured strengthening of [KL88]. Finally we see a recent proof of this conjecture, hence completing Dadush's algorithm.
This is joint work with Victor Reis.
