{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:37Z","timestamp":1750309477175,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585139","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1834-1847","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Cheeger Inequalities for Directed Graphs and Hypergraphs using Reweighted Eigenvalues"],"prefix":"10.1145","author":[{"given":"Lap Chi","family":"Lau","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kam Chuen","family":"Tung","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Wang","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590"},{"key":"e_1_3_2_1_2_1","unstructured":"David Aldous and James Fill. 2002. Reversible markov chains and random walks on graphs. (Unfinished monograph). \t\t\t\t  David Aldous and James Fill. 2002. Reversible markov chains and random walks on graphs. (Unfinished monograph)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178123"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.03.032"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21398-9_3"},{"key":"e_1_3_2_1_11_1","unstructured":"Jef Cheeger. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis ( 1970 ) 195-199. \t\t\t\t  Jef Cheeger. 1970. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis ( 1970 ) 195-199."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00015"},{"volume-title":"Spectral graph theory","author":"Chung Fan","key":"e_1_3_2_1_13_1","unstructured":"Fan Chung . 1997. Spectral graph theory . Vol. 92 . American Mathematical Society . Fan Chung. 1997. Spectral graph theory. Vol. 92. American Mathematical Society."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055463"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.69"},{"key":"e_1_3_2_1_17_1","volume-title":"In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 983-992","author":"Cucuringu Mihai","year":"2020","unstructured":"Mihai Cucuringu , Huan Li , He Sun , and Luca Zanetti . 2020 . Hermitian matrices for clustering directed graphs: insights and applications . In In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 983-992 . Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. 2020. Hermitian matrices for clustering directed graphs: insights and applications. In In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 983-992."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897654"},{"key":"e_1_3_2_1_19_1","unstructured":"James Allen Fill. 1991. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains with an application to the exclusion process. The Annals of Applied Probability ( 1991 ) 62-87. \t\t\t\t  James Allen Fill. 1991. Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains with an application to the exclusion process. The Annals of Applied Probability ( 1991 ) 62-87."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Murali Krishnan Ganapathy. 2006. Robust Mixing. Ph. D. Dissertation. University of Chicago. \t\t\t\t  Murali Krishnan Ganapathy. 2006. Robust Mixing. Ph. D. Dissertation. University of Chicago.","DOI":"10.1007\/11830924_33"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22057"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/s0273-0979-06-01126-8"},{"key":"e_1_3_2_1_23_1","volume-title":"Huy Tuan Pham, and Thuy-Duong Vuong","author":"Jain Vishesh","year":"2022","unstructured":"Vishesh Jain , Huy Tuan Pham, and Thuy-Duong Vuong . 2022 . Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain . arXiv preprint arXiv:2203.03858 ( 2022 ). Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. 2022. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain. arXiv preprint arXiv:2203.03858 ( 2022 )."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00114"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488611"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00042"},{"key":"e_1_3_2_1_27_1","unstructured":"Steinar Laenen and He Sun. 2020. Higher-order spectral clustering of directed graphs. Advances in Neural Information Processing Systems (NeurIPS) 33 ( 2020 ) 941-951. \t\t\t\t  Steinar Laenen and He Sun. 2020. Higher-order spectral clustering of directed graphs. Advances in Neural Information Processing Systems (NeurIPS) 33 ( 2020 ) 941-951."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214078"},{"key":"e_1_3_2_1_29_1","volume-title":"Levin and Yuval Peres","author":"David","year":"2017","unstructured":"David A. Levin and Yuval Peres . 2017 . Markov chains and mixing times. Vol. 107 . American Mathematical Society . David A. Levin and Yuval Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Society."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.71"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning. PMLR, 3014-3023","author":"Li Pan","year":"2018","unstructured":"Pan Li and Olgica Milenkovic . 2018 . Submodular hypergraphs:-laplacians, cheeger inequalities and spectral clustering . In Proceedings of the 35th International Conference on Machine Learning. PMLR, 3014-3023 . Pan Li and Olgica Milenkovic. 2018. Submodular hypergraphs:-laplacians, cheeger inequalities and spectral clustering. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 3014-3023."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2014.10.028"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746555"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.46"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.109"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v10-1169"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536452"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835785"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.160"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585139","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585139","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585139"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":42,"alternative-id":["10.1145\/3564246.3585139","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585139","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}