{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:40Z","timestamp":1740109600694,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:00:00Z","timestamp":1710547200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T00:00:00Z","timestamp":1710547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NSF","award":["CCF 1553751"],"award-info":[{"award-number":["CCF 1553751"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00454-024-00636-y","type":"journal-article","created":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T21:21:00Z","timestamp":1710624060000},"page":"1647-1674","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Spectral Approach to Polytope Diameter"],"prefix":"10.1007","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4331-8794","authenticated-orcid":false,"given":"Hariharan","family":"Narayanan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rikhav","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikhil","family":"Srivastava","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,16]]},"reference":[{"key":"636_CR1","first-page":"1205","volume":"2","author":"AD Alexandrov","year":"1937","unstructured":"Alexandrov, A.D.: Zur theorie der gemischten volumina von konvexen k\u00f6rpern ii. Mat. Sbornik N.S. 2, 1205\u20131238 (1937)","journal-title":"Mat. Sbornik N.S."},{"key":"636_CR2","first-page":"227","volume":"3","author":"AD Alexandrov","year":"1938","unstructured":"Alexandrov, A.D.: Zur theorie der gemischten volumina von konvexen k\u00f6rpern iv. Mat. Sbornik N.S. 3, 227\u2013251 (1938)","journal-title":"Mat. Sbornik N.S."},{"key":"636_CR3","doi-asserted-by":"crossref","unstructured":"Anari, N., Liu, K., Gharan, S.O., Vinzant, C.: Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In: STOC\u201919\u2014Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (pp. 1\u201312). ACM, New York (2019)","DOI":"10.1145\/3313276.3316385"},{"key":"636_CR4","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0012-365X(74)90016-8","volume":"10","author":"D Barnette","year":"1974","unstructured":"Barnette, D.: An upper bound for the diameter of a polytope. Discret. Math. 10, 9\u201313 (1974)","journal-title":"Discret. Math."},{"issue":"1","key":"636_CR5","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/s00454-014-9601-x","volume":"52","author":"N Bonifas","year":"2014","unstructured":"Bonifas, N., Di Summa, M., Eisenbrand, F., H\u00e4hnle, N., Niemeier, M.: On sub-determinants and the diameter of polyhedra. Discrete Comput. Geom. 52(1), 102\u2013115 (2014)","journal-title":"Discrete Comput. Geom."},{"key":"636_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s186-1999-8373-5","volume":"49","author":"K Borgwardt","year":"1999","unstructured":"Borgwardt, K., Huhn, P.: A lower bound on the average number of pivot-steps for solving linear programs valid for all variants of the simplex-algorithm. Math. Methods OR 49, 175\u2013210 (1999)","journal-title":"Math. Methods OR"},{"key":"636_CR7","unstructured":"Borgwardt, K.-H.: Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der linearen Optimierung. In: 2nd Symposium on Operations Research (Rheinisch-Westf\u00e4lische Tech. Hochsch. Aachen, Aachen, 1977), Teil 1, Operations Res. Verfahren, XXVIII, pp. 332\u2013345. Hain, K\u00f6nigstein\/Ts (1978)"},{"key":"636_CR8","doi-asserted-by":"crossref","unstructured":"Borgwardt, K.-H.: The Simplex Method. Algorithms and Combinatorics: Study and Research Texts, vol. 1. Springer, Berlin (1987). A probabilistic analysis","DOI":"10.1007\/978-3-642-61578-8_1"},{"key":"636_CR9","doi-asserted-by":"crossref","unstructured":"Brunsch, T., R\u00f6glin, H.: Finding short paths on polytopes by the shadow vertex algorithm. In: Automata, Languages, and Programming. Part I. Lecture Notes in Computer Sciences, vol. 7965, pp. 279\u2013290. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-39206-1_24"},{"issue":"2","key":"636_CR10","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1090\/S0894-0347-1989-0965008-X","volume":"2","author":"FRK Chung","year":"1989","unstructured":"Chung, F.R.K.: Diameters and eigenvalues. J. Am. Math. Soc. 2(2), 187\u2013196 (1989)","journal-title":"J. Am. Math. Soc."},{"issue":"4","key":"636_CR11","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1007\/s00454-016-9793-3","volume":"56","author":"D Dadush","year":"2016","unstructured":"Dadush, D., H\u00e4hnle, N.: On the shadow simplex method for curved polyhedra. Discrete Comput. Geom. 56(4), 882\u2013909 (2016)","journal-title":"Discrete Comput. Geom."},{"key":"636_CR12","doi-asserted-by":"publisher","DOI":"10.1137\/18M119720","author":"D Dadush","year":"2020","unstructured":"Dadush, D., Huiberts, S.: A friendly smoothed analysis of the simplex method. SIAM J. Comput. (2020). https:\/\/doi.org\/10.1137\/18M119720","journal-title":"SIAM J. Comput."},{"key":"636_CR13","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Spielman, D.A.: Improved smoothed analysis of the shadow vertex simplex method. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pages 349\u2013356 (2005)","DOI":"10.1109\/SFCS.2005.44"},{"issue":"1, , Ser. A","key":"636_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582563","volume":"64","author":"M Dyer","year":"1994","unstructured":"Dyer, M., Frieze, A.: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64(1, Ser. A), 1\u201316 (1994)","journal-title":"Math. Program."},{"issue":"1\u20132, , Ser. A","key":"636_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10107-016-1089-0","volume":"164","author":"F Eisenbrand","year":"2017","unstructured":"Eisenbrand, F., Vempala, S.: Geometric random edge. Math. Program. 164(1\u20132, Ser. A), 325\u2013339 (2017)","journal-title":"Math. Program."},{"key":"636_CR16","unstructured":"Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes. Oxford University Press, Oxford (2020). 4th edn [of 0667520]"},{"key":"636_CR17","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s11856-010-0070-5","volume":"178","author":"I Izmestiev","year":"2010","unstructured":"Izmestiev, I.: The Colin de Verdi\u00e8re number and graphs of polytopes. Isr. J. Math. 178, 427\u2013444 (2010)","journal-title":"Isr. J. Math."},{"issue":"2","key":"636_CR18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1090\/S0273-0979-1992-00285-9","volume":"26","author":"G Kalai","year":"1992","unstructured":"Kalai, G., Kleitman, D.J.: A quasi-polynomial bound for the diameter of graphs of polyhedra. Bull. Am. Math. Soc. (N.S.) 26(2), 315\u2013316 (1992)","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"issue":"20","key":"636_CR19","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1112\/plms\/s3-20.1.161","volume":"3","author":"DG Larman","year":"1970","unstructured":"Larman, D.G.: Paths of polytopes. Proc. Lond. Math. Soc. 3(20), 161\u2013178 (1970)","journal-title":"Proc. Lond. Math. Soc."},{"key":"636_CR20","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF01244313","volume":"113","author":"P McMullen","year":"1993","unstructured":"McMullen, P.: On simple polytopes. Invent. Math. 113, 419\u2013444 (1993)","journal-title":"Invent. Math."},{"key":"636_CR21","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/BF02711515","volume":"15","author":"P McMullen","year":"1996","unstructured":"McMullen, P.: Weights on polytopes. Discrete Comput. Geom. 15, 363\u2013388 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"636_CR22","doi-asserted-by":"crossref","unstructured":"Mihail, M.: On the expansion of combinatorial polytopes. In: Mathematical Foundations of Computer Science 1992 (Prague, 1992). Lecture Notes in Computer Science, vol. 629, pp. 37\u201349. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55808-X_4"},{"issue":"1, (Ser. B)","key":"636_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01589099","volume":"45","author":"D Naddef","year":"1989","unstructured":"Naddef, D.: The Hirsch conjecture is true for $$(0,1)$$-polytopes. Math. Program. 45(1, (Ser. B)), 109\u2013110 (1989)","journal-title":"Math. Program."},{"key":"636_CR24","unstructured":"Narayanan, H., Shah, R., Srivastava, N.: A spectral approach to polytope diameter. arXiv preprint (2021). arXiv:2101.12198"},{"issue":"1","key":"636_CR25","doi-asserted-by":"publisher","first-page":"383","DOI":"10.4007\/annals.2012.176.1.7","volume":"176","author":"F Santos","year":"2012","unstructured":"Santos, F.: A counterexample to the Hirsch conjecture. Ann. Math. 176(1), 383\u2013412 (2012)","journal-title":"Ann. Math."},{"key":"636_CR26","doi-asserted-by":"crossref","unstructured":"Schneider, R.: Polytopes and Brunn\u2013Minkowski theory. In: Polytopes: Abstract, Convex and Computational (Scarborough, ON, 1993). NATO Advanced Study Institute, Nonstandard Analysis and Its Applications, vol. 440, pp. 273\u2013299. Kluwer, Dordrecht (1994)","DOI":"10.1007\/978-94-011-0924-6_13"},{"key":"636_CR27","unstructured":"Schneider, R.: Convex Bodies: The Brunn\u2013Minkowski Theory. Encyclopedia of Mathematics and Its Applications, vol. 151, expanded edn. Cambridge University Press, Cambridge (2014)"},{"issue":"5","key":"636_CR28","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1007\/BF01014892","volume":"51","author":"AD Sokal","year":"1988","unstructured":"Sokal, A.D., Thomas, L.E.: Absence of mass gap for a class of stochastic contour models. J. Stat. Phys. 51(5), 907\u2013947 (1988)","journal-title":"J. Stat. Phys."},{"issue":"3","key":"636_CR29","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"636_CR30","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0001-8708(80)90050-X","volume":"35","author":"RP Stanley","year":"1980","unstructured":"Stanley, R.P.: The numbers of faces of a simplicial convex polytope. Adv. Math. 35, 236\u2013238 (1980)","journal-title":"Adv. Math."},{"issue":"3","key":"636_CR31","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00454-018-0016-y","volume":"62","author":"N Sukegawa","year":"2019","unstructured":"Sukegawa, N.: An asymptotically improved upper bound on the diameter of polyhedra. Discrete Comput. Geom. 62(3), 690\u2013699 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"636_CR32","doi-asserted-by":"crossref","unstructured":"Timorin, V.A.: An analogue of the Hodge\u2013Riemann relations for simple convex polyhedra. Uspekhi Mat. Nauk, 54(2(326)), 113\u2013162 (1999)","DOI":"10.4213\/rm134"},{"issue":"4","key":"636_CR33","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1137\/140962310","volume":"28","author":"MJ Todd","year":"2014","unstructured":"Todd, M.J.: An improved Kalai\u2013Kleitman bound for the diameter of a polyhedron. SIAM J. Discret. Math. 28(4), 1944\u20131947 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"1\u20132","key":"636_CR34","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1080\/03081089508818378","volume":"39","author":"ER Van Dam","year":"1995","unstructured":"Van Dam, E.R., Haemers, W.H.: Eigenvalues and the diameter of graphs. Linear Multilinear Algebra 39(1\u20132), 33\u201344 (1995)","journal-title":"Linear Multilinear Algebra"},{"issue":"2","key":"636_CR35","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1137\/070683386","volume":"39","author":"R Vershynin","year":"2009","unstructured":"Vershynin, R.: Beyond Hirsch conjecture: walks on random polytopes and smoothed complexity of the simplex method. SIAM J. Comput. 39(2), 646\u2013678 (2009)","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00636-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00636-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00636-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T22:02:24Z","timestamp":1731794544000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00636-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,16]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["636"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00636-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,3,16]]},"assertion":[{"value":"3 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}