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

Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes

PDF

arXiv

BibTeX

@article{BDGHL21,
  title = {Asymptotic Bounds on the Combinatorial Diameter of Random Polytopes},
  ISSN = {1432-0444},
  DOI = {10.1007/s00454-025-00814-6},
  journal = {Discrete and Computational Geometry},
  publisher = {Springer Science and Business Media LLC},
  author = {Bonnet,  Gilles and Dadush,  Daniel and Grupel,  Uri and Huiberts,  Sophie and Livshyts,  Galyna},
  year = {2026},
  month = feb,
  note = {preliminary version in SoCG 2022}
}
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