Publications

Smoothed Analysis of the Simplex Method

Joint work with Daniel Dadush.

Invited chapter in Beyond Worst Case Analysis (editor Tim Roughgarden), 2020+.

PDF here.

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.

PDF here. Slides here.

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 here.

A Friendly Smoothed Analysis of the Simplex Method

Joint work with Daniel Dadush.

Published in 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018.

Full version to appear in siopt special issue (invited). Updated June 2019 to include a new algorithm, improving running time when σ is large.

PDF here. Slides here.