(home)   //   (publications)   //   (blog)   //   (scans from the library)

Sophie Huiberts

Papers

Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book (Aug 2026)
Optimal Smoothed Analysis of the Simplex Method (Aug 2026)
An unconditional lower bound for the active-set method in convex quadratic maximization (Jul 2025)
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method (Nov 2022)
A nearly optimal randomized algorithm for explorable heap selection (Oct 2022)
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes (Dec 2021)
On the Integrality Gap of Binary Integer Programs with Gaussian Data (Dec 2020)
A Simple Method for Convex Optimization in the Oracle Model (Nov 2020)
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix (Dec 2019)
A Friendly Smoothed Analysis of the Simplex Method (Nov 2017)

Chapters

1. Smoothed Analysis of the Simplex Method
   with Daniel Dadush.
   Book chapter in Beyond the Worst-Case Analysis of Algorithms, ed. Tim Roughgarden, 2021.

Theses

1. Geometric Aspects of Linear Programming: Shadow Paths, Central Paths, and a Cutting Plane Method
   PhD thesis.
   Stieltjes Prize for best Dutch PhD thesis in mathematics. Gijs de Leve Prize for best Dutch PhD thesis in operations research.
2. How Large is the Shadow? Smoothed Analysis of the Simplex Method
   Master thesis.
   Thesis for the master’s programme Mathematical Sciences at Utrecht University. Finalist (top 3) for Faculty of Science master thesis prize.

Miscellaneous

1. Het Dieetprobleem
   STAtOR, July 2025. video
2. Prizes and Prejudice
   Bulletin of the EATCS, 2022.
3. Wanneer is software snel?
   AG Connect, 2021.

Collaborators

Thanks to all my collaborators: Eleon Bach, Alex Black, Gilles Bonnet, Sander Borst, Daniel Dadush, Yann Disser, Uri Grupel, Christopher Hojny, Danish Kashaev, Sean Kafer, Yin Tat Lee, Galyna Livshyts, Nils Mosis, Bento Natura, Samarth Tiwari, László Végh, Stefan Weltge, Xinzhi Zhang.