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

Sophie Huiberts

Papers

Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book (Aug 2026)
 Eleon Bach, Alexander Black, Sean Kafer
 STOC 2026 / arXiv / code / talk / bibTeX
Optimal Smoothed Analysis of the Simplex Method (Aug 2026)
 Eleon Bach
 FOCS 2025 / arXiv / video / bibTeX
An unconditional lower bound for the active-set method in convex quadratic maximization (Jul 2025)
 Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis
 SODA 2026 / arXiv / bibTeX
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method (Nov 2022)
 Xinzhi Zhang, Yin Tat Lee
 STOC 2023, TheoretiCS / arXiv / video / bibTeX
A nearly optimal randomized algorithm for explorable heap selection (Oct 2022)
 Sander Borst, Daniel Dadush, Sophie Huiberts, Danish Kashaev.
 IPCO 2023, Mathematical Programming / arXiv / talk / bibTeX
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes (Dec 2021)
 Gilles Bonnet, Daniel Dadush, Uri Grupel, Sophie Huiberts, Galyna Livshyts.
 SOCG 2022, Discrete and Computational Geometry / arXiv / talk / bibTeX
On the Integrality Gap of Binary Integer Programs with Gaussian Data (Dec 2020)
 Sander Borst, Daniel Dadush, Sophie Huiberts, Samarth Tiwari.
 IPCO 2021, Mathematical Programming / arXiv / bibTeX
A Simple Method for Convex Optimization in the Oracle Model (Nov 2020)
 Daniel Dadush, Christopher Hojny, Sophie Huiberts, Stefan Weltge.
 IPCO 2022, Mathematical Programming / arXiv / talk / bibTeX
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix (Dec 2019)
 Daniel Dadush, Sophie Huiberts, Bento Natura, László Végh.
 IPCO 2021, Mathematical Programming / arXiv / talk / bibTeX
A Friendly Smoothed Analysis of the Simplex Method (Nov 2017)
 Daniel Dadush, Sophie Huiberts.
 STOC 2018, SIAM Journal on Computing / arXiv / talk / bibTeX

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.