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

An unconditional lower bound for the active-set method in convex quadratic maximization

PDF

arXiv

BibTeX

@InProceedings{BDHM25,
  title = {An Unconditional Lower Bound for the Active-Set Method in Convex Quadratic Maximization},
  DOI = {10.1137/1.9781611978971.14},
  booktitle = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
  publisher = {Society for Industrial and Applied Mathematics},
  author = {Bach,  Eleon and Disser,  Yann and Huiberts,  Sophie and Mosis,  Nils},
      eprint={2507.16648},
      archivePrefix={arXiv},
  year = {2026},
  month = jan,
  pages = {314–327}
}

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