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

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method

PDF

arXiv

BibTeX

@article{HLZ22,
    title      = {Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method},
    author     = {Sophie Huiberts and Yin Tat Lee and Xinzhi Zhang},
    doi        = {10.46298/theoretics.25.23},
    journal    = {TheoretiCS},
    issn       = {2751-4838},
    volume     = {Volume 4},
    eid        = 23,
    year       = {2025},
    month      = {Oct},
  eprint={2211.11860},
  archivePrefix={arXiv},
}
Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book (Oct 2025)
Eleon Bach, Alexander Black, Sean Kafer
STOC 2026 / arXiv / code / talk / bibTeX
Optimal Smoothed Analysis of the Simplex Method (May 2025)
Eleon Bach
FOCS 2025 / arXiv / video / 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
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
A Friendly Smoothed Analysis of the Simplex Method (Nov 2017)
Daniel Dadush, Sophie Huiberts.
STOC 2018, SIAM Journal on Computing / arXiv / talk / bibTeX