{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:48:52Z","timestamp":1776206932993,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,9,1]]},"abstract":"<jats:p>The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic. The framework of smoothed analysis, first introduced by Spielman and Teng (JACM '04) for this purpose, defines the smoothed complexity of solving a linear program with $d$ variables and $n$ constraints as the expected running time when Gaussian noise of variance $\u03c3^2$ is added to the LP data. We prove that the smoothed complexity of the simplex method is $O(\u03c3^{-3\/2} d^{13\/4}\\log^{7\/4} n)$, improving the dependence on $1\/\u03c3$ compared to the previous bound of $O(\u03c3^{-2} d^2\\sqrt{\\log n})$. We accomplish this through a new analysis of the \\emph{shadow bound}, key to earlier analyses as well. Illustrating the power of our new method, we use our method to prove a nearly tight upper bound on the smoothed complexity of two-dimensional polygons.   We also establish the first non-trivial lower bound on the smoothed complexity of the simplex method, proving that the \\emph{shadow vertex simplex method} requires at least $\u03a9\\Big(\\min \\big(\u03c3^{-1\/2} d^{-1\/2}\\log^{-1\/4} d,2^d \\big) \\Big)$ pivot steps with high probability. A key part of our analysis is a new variation on the extended formulation for the regular $2^k$-gon. We end with a numerical experiment that suggests this analysis could be further improved.<\/jats:p><jats:p>56 pages. This is the TheoretiCS journal version<\/jats:p>","DOI":"10.46298\/theoretics.25.23","type":"journal-article","created":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T08:10:13Z","timestamp":1760515813000},"source":"Crossref","is-referenced-by-count":1,"title":["Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method"],"prefix":"10.46298","volume":"Volume 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2633-014X","authenticated-orcid":false,"given":"Sophie","family":"Huiberts","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xinzhi","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2025,10,15]]},"container-title":["TheoretiCS"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2211.11860v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2211.11860v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T08:10:14Z","timestamp":1760515814000},"score":1,"resource":{"primary":{"URL":"https:\/\/theoretics.episciences.org\/13604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,15]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/theoretics.25.23","relation":{"has-preprint":[{"id-type":"arxiv","id":"2211.11860v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2211.11860","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2211.11860","asserted-by":"subject"}]},"ISSN":["2751-4838"],"issn-type":[{"value":"2751-4838","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,15]]},"article-number":"13604"}}