{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:04:46Z","timestamp":1765793086814,"version":"3.48.0"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"name":"Science and Technology Innovation 2030","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61932002"],"award-info":[{"award-number":["61932002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009002","name":"Shanghai University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"DOI":"10.1137\/22m1534407","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:01:17Z","timestamp":1765792877000},"page":"1568-1625","source":"Crossref","is-referenced-by-count":0,"title":["Cheeger\u2019s Inequalities for Vertex Expansion and Reweighted Eigenvalues"],"prefix":"10.1137","volume":"54","author":[{"given":"Tsz Chiu","family":"Kwok","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Shanghai University of Finance and Economics, Shanghai, China."}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada."}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8399-2564","authenticated-orcid":true,"given":"Kam Chuen","family":"Tung","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada."}]}],"member":"351","published-online":{"date-parts":[[2025,12,15]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"N. Anari, K. Liu, S. O. Gharan, and C. Vinzant, Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid, in Proceedings of the 51st Annual Symposium on Theory of Computing (STOC), 2019, pp. 1\u201312.","DOI":"10.1145\/3313276.3316385"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"S. Arora, B. Barak, and D. Steurer, Subexponential algorithms for unique games and related problems, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 563\u2013572.","DOI":"10.1109\/FOCS.2010.59"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"S. Arora and R. Ge, New tools for graph coloring, in Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), 2011, pp. 1\u201312.","DOI":"10.1007\/978-3-642-22935-0_1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1017\/9781009701853.002"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070018"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/070689413"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2006.11920281"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3178123"},{"key":"ref14","unstructured":"T.H. H. Chan, Z. G. Tang, X. Wu, and C. Zhang. Diffusion Operator and Spectral Analysis for Directed Hypergraph Laplacian, CoRR abs\/1711.01560, 2017."},{"key":"ref15","first-page":"195","volume-title":"Problems in Analysis","author":"Cheeger J.","year":"1970"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2322942"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1965.264137"},{"key":"ref18","unstructured":"M. Farhadi, A. Louis, and P. Tetali, On the Complexity of \\(\\lambda_{\\infty }\\), Vertex Expansion, and Spread Constant of Trees, https:\/\/arxiv.org\/abs\/2003.05582v2, 2020."},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Mihail, Balanced matroids, in Proceedings of the 24th Annual Symposium on Theory of Computing (STOC), 1992, pp. 26\u201338.","DOI":"10.1145\/129712.129716"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1214\/12-AAP886"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22015-9"},{"key":"ref23","unstructured":"R. Gillmann, 0\/1-Polytopes: Typical and Extremal Properties, Ph.D. thesis, Technische Universit\u00e4t Berlin, 2007."},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer, and J. R. Lee, Bounded geometries, fractals, and low-distortion embeddings, in Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003, pp. 534\u2013543.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"ref25","volume-title":"Matrix Analysis","author":"Horn R. A.","year":"2013"},{"key":"ref26","unstructured":"V. Jain, H. T. Pham, and T.D. Vuong, Dimension Reduction for Maximum Matchings and the Fastest Mixing Markov Chain, https:\/\/arxiv.org\/abs\/2203.03858, 2022."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718805.ch13"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"V. Kaibel and A. Remshagen, On the graph-density of random \\(0\/1\\)-polytopes, in Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003, pp. 318\u2013328.","DOI":"10.1007\/978-3-540-45198-3_27"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"T. C. Kwok, L. C. Lau, Y. T. Lee, S. O. Gharan, and L. Trevisan, Improved Cheeger\u2019s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap, in Proceedings of the 45th Annual Symposium on Theory of Computing (STOC), 2013, pp. 11\u201320.","DOI":"10.1145\/2488608.2488611"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1015957395"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"J. R. Lee, S. O. Gharan, and L. Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities, in Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), 2012, pp. 1117\u20131130.","DOI":"10.1145\/2213977.2214078"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.3923\/ajms.2011.66.70"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"A. Louis, Hypergraph Markov operators, eigenvalues and approximation algorthms, in Proceedings of the 47th Annual Symposium on Theory of Computing (STOC), 2015, pp. 713\u2013722.","DOI":"10.1145\/2746539.2746555"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"A. Louis, P. Raghavendra, P. Tetali, and S. Vempala, Many sparse cuts via higher eigenvalues, in Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012, pp. 1131\u20131140.","DOI":"10.1145\/2213977.2214079"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"A. Louis, P. Raghavendra, and S. Vempala, The complexity of approximating vertex expansion, in Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2013, pp. 360\u2013369.","DOI":"10.1109\/FOCS.2013.46"},{"key":"ref37","unstructured":"S. Olesker-Taylor and L. Zanetti, Geometric bounds on the fastest mixing Markov chain, in Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022."},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"P. Raghavendra and D. Steurer, Graph expansion and the unique games conjecture, in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010, pp. 755\u2013764.","DOI":"10.1145\/1806689.1806792"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v10-1169"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-3557-3_1"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"ref42","unstructured":"D. Steurer, On the Complexity of Unique Games and Graph Expansion, Ph.D. thesis, Princeton University, Princeton, NJ, 2010."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"ref44","volume-title":"SIAM","author":"Strang G.","year":"2016"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.119.07.606"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"L. Trevisan, Max cut and the smallest eigenvalue, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 263\u2013272.","DOI":"10.1145\/1536414.1536452"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T10:01:24Z","timestamp":1765792884000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1534407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,15]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/22M1534407"],"URL":"https:\/\/doi.org\/10.1137\/22m1534407","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,15]]}}}