Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
Joint work with Yin Tat Lee, Xinzhi Zhang.
Conference version in STOC 2023.
Publications
A Nearly Optimal Randomized Algorithm for Explorable Heap Selection
Joint work with Sander Borst, Daniel Dadush, Danish Kashaev.
Conference version in IPCO 2023.
A Simple Method for Convex Optimization in the Oracle Model
Joint work with Daniel Dadush, Christopher Hojny, Stefan Weltge.
Conference version in IPCO 2022. Journal version in Mathematical Programming.
Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes
Joint work with Gilles Bonnet, Daniel Dadush, Uri Grupel, Galyna Livshyts.
Conference version in SOCG 2022. Journal version to appear in Discrete and Computational Geometry.
Geometric Aspects of Linear Programming: Shadow Paths, Central Paths, and a Cutting Plane Method
Stieltjes Prize for best Dutch PhD thesis in mathematics. Gijs de Leve Prize for best Dutch PhD thesis in operations research.
PDF.
Smoothed Analysis of the Simplex Method
Joint work with Daniel Dadush.
Book chapter in Beyond the Worst-Case Analysis of Algorithms, ed. Tim Roughgarden, 2021.
PDF.
On the Integrality Gap of Binary Integer Programs with Gaussian Data
Joint work with Sander Borst, Daniel Dadush, Samarth Tiwari.
Conference version in IPCO 2021. Journal version in Mathematical Programming.
PDF.
A Scaling-Invariant Algorithm for Linear Programming Whose Running Time Depends Only on the Constraint Matrix
Joint work with Daniel Dadush, Bento Natura and László Végh.
Conference version in STOC 2020. Journal version in Mathematical Programming.
How Large is the Shadow? Smoothed Analysis of the Simplex Method
Thesis for the master’s programme Mathematical Sciences at Utrecht University. Finalist (top 3) for Faculty of Science master thesis prize.
PDF.
A Friendly Smoothed Analysis of the Simplex Method
Joint work with Daniel Dadush.
Conference version in STOC 2018. Journal version in SIAM Journal on Computing.