Title:Smoothed analysis of the simplex method

Speaker: Sophie Huiberts 
National Centre for Scientific Research (CNRS), France

Summary:
The simplex method is an important algorithm for solving linear programming problems. Despite nearly 8 decades of use, its running time is still poorly understood. In this talk I will describe recent results about smoothed analysis, the current state-of-the-art framework for analyzing this algorithm’s performance. In recent work (to appear in FOCS 2025) we derived matching upper and lower bounds under this framework. I will describe the basic results and discuss where to go next, now that smoothed analysis is finished.

Biography:
Sophie is a permanent researcher at CNRS in France, where she is hosted by the LIMOS lab in Clermont-Ferrand. She was previously a Simons Junior Fellow at Columbia University. She completed her PhD research at CWI in Amsterdam. For her PhD thesis she was awarded the Gijs de Leve prize and the Stieltjes Prize. 

JOIN ON ZOOM – MEETING ID: 873 1557 5255; PASSWORD: 778635

WED 20 AUGUST 2025 16:00 -17:00 (AEST, Australian Eastern Standard Time)/ 08:00 – 09:00 (CEST, Central European Summer Time)