{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T23:22:50Z","timestamp":1783984970114,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC","award":["2950-120715"],"award-info":[{"award-number":["2950-120715"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384317","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1198-1211","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Improved analysis of higher order random walks and applications"],"prefix":"10.1145","author":[{"given":"Vedat Levi","family":"Alev","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-06-03833-5"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2018.188.2.1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.85"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00021"},{"key":"e_1_3_2_1_5_1","first-page":"82","article-title":"Random walks on finite groups and rapidly mixing markov chains","author":"Aldous David","year":"1981","unstructured":"David Aldous . Random walks on finite groups and rapidly mixing markov chains . In S\u00e9minaire de Probabilit\u00e9s XVII 1981 \/ 82 , pages 243\u2013297. Springer, 1983. David Aldous. Random walks on finite groups and rapidly mixing markov chains. In S\u00e9minaire de Probabilit\u00e9s XVII 1981\/82, pages 243\u2013297. Springer, 1983.","journal-title":"S\u00e9minaire de Probabilit\u00e9s"},{"key":"e_1_3_2_1_6_1","unstructured":"Nima Anari Kuikui Liu and Shayan Oveis Gharan. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model (Manuscript).  Nima Anari Kuikui Liu and Shayan Oveis Gharan. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model (Manuscript)."},{"key":"e_1_3_2_1_7_1","first-page":"12","volume-title":"STOC","author":"Anari Nima","unstructured":"Nima Anari , Kuikui Liu , Shayan Oveis Gharan , and Cynthia Vinzant . Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid . In STOC , pages 1\u2013 12 . ACM, 2019. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid. In STOC, pages 1\u201312. ACM, 2019."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646111"},{"key":"e_1_3_2_1_9_1","volume-title":"Lorentzian polynomials. arXiv preprint arXiv:1902.03719","author":"Br\u00e4nd\u00e9n Petter","year":"2019","unstructured":"Petter Br\u00e4nd\u00e9n and June Huh . Lorentzian polynomials. arXiv preprint arXiv:1902.03719 , 2019 . Petter Br\u00e4nd\u00e9n and June Huh. Lorentzian polynomials. arXiv preprint arXiv:1902.03719, 2019."},{"key":"e_1_3_2_1_10_1","volume-title":"Matrix analysis","author":"Bhatia Rajendra","year":"2013","unstructured":"Rajendra Bhatia . Matrix analysis , volume 169 . Springer Science & Business Media , 2013 . Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-006-0016-3"},{"key":"e_1_3_2_1_12_1","volume-title":"Modified log-sobolev inequalities for strongly log-concave distributions. CoRR, abs\/1903.06081","author":"Cryan Mary","year":"2019","unstructured":"Mary Cryan , Heng Guo , and Giorgos Mousa . Modified log-sobolev inequalities for strongly log-concave distributions. CoRR, abs\/1903.06081 , 2019 . Mary Cryan, Heng Guo, and Giorgos Mousa. Modified log-sobolev inequalities for strongly log-concave distributions. CoRR, abs\/1903.06081, 2019."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00088"},{"key":"e_1_3_2_1_14_1","first-page":"20","volume-title":"APPROX\/RANDOM","author":"Dikstein Yotam","year":"2018","unstructured":"Yotam Dikstein , Irit Dinur , Yuval Filmus , and Prahladh Harsha . Boolean function analysis on high-dimensional expanders . In APPROX\/RANDOM , pages 38:1\u201338: 20 , 2018 . Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean function analysis on high-dimensional expanders. In APPROX\/RANDOM, pages 38:1\u201338:20, 2018."},{"key":"e_1_3_2_1_15_1","volume-title":"A random polynomial-time algorithm for approximating the","author":"Dyer Martin","year":"1991","unstructured":"Martin Dyer , Alan Frieze , and Ravi Kannan . A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1\u2013 17 , 1991 . Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1\u201317, 1991."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.129"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_2_1_18_1","first-page":"10","volume-title":"SOCG","author":"Dotterrer Dominic","year":"2016","unstructured":"Dominic Dotterrer , Tali Kaufman , and Uli Wagner . On expansion and topological overlap . In SOCG , pages 35:1\u201335: 10 , 2016 . Dominic Dotterrer, Tali Kaufman, and Uli Wagner. On expansion and topological overlap. In SOCG, pages 35:1\u201335:10, 2016."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034968224"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897543"},{"key":"e_1_3_2_1_21_1","first-page":"1197","volume-title":"SODA","author":"Fox Jacob","year":"2011","unstructured":"Jacob Fox , Mikhail Gromov , Vincent Lafforgue , Assaf Naor , and J\u00e1nos Pach . Overlap properties of geometric expanders . In SODA , pages 1188\u2013 1197 , 2011 . Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and J\u00e1nos Pach. Overlap properties of geometric expanders. In SODA, pages 1188\u20131197, 2011."},{"key":"e_1_3_2_1_22_1","first-page":"38","volume-title":"Proceedings of the Twenty Fourth Annual ACM Symposium on the Theory of Computing","author":"Feder Tom","unstructured":"Tom Feder and Milena Mihail . Balanced matroids . In Proceedings of the Twenty Fourth Annual ACM Symposium on the Theory of Computing , pages 26\u2013 38 . Citeseer, 1992. Tom Feder and Milena Mihail. Balanced matroids. In Proceedings of the Twenty Fourth Annual ACM Symposium on the Theory of Computing, pages 26\u201338. Citeseer, 1992."},{"key":"e_1_3_2_1_23_1","unstructured":"Chris Godsil. Mathematics stackexchange url: https:\/\/math.stackexchange.com\/questions\/2527245\/what-graph-have-exactly-one-positive-eigenvalue .  Chris Godsil. Mathematics stackexchange url: https:\/\/math.stackexchange.com\/questions\/2527245\/what-graph-have-exactly-one-positive-eigenvalue ."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0073-8"},{"key":"e_1_3_2_1_25_1","first-page":"46","volume-title":"FOCS","author":"Hayes Thomas P","unstructured":"Thomas P Hayes . A simple condition implying rapid mixing of single-site dynamics on spin systems . In FOCS , pages 39\u2013 46 . IEEE, 2006. Thomas P Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In FOCS, pages 39\u201346. IEEE, 2006."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4310\/ACTA.2017.v218.n2.a2"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000639"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-016-0362-y"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554842"},{"key":"e_1_3_2_1_35_1","volume-title":"Walking on the edge and cosystolic expansion. CoRR, abs\/1606.01844","author":"Kaufman Tali","year":"2016","unstructured":"Tali Kaufman and David Mass . Walking on the edge and cosystolic expansion. CoRR, abs\/1606.01844 , 2016 . Tali Kaufman and David Mass. Walking on the edge and cosystolic expansion. CoRR, abs\/1606.01844, 2016."},{"key":"e_1_3_2_1_36_1","first-page":"27","volume-title":"ITCS","author":"Kaufman Tali","year":"2017","unstructured":"Tali Kaufman and David Mass . High dimensional random walks and colorful expansion . In ITCS , pages 4:1\u20134: 27 , 2017 . Tali Kaufman and David Mass. High dimensional random walks and colorful expansion. In ITCS, pages 4:1\u20134:27, 2017."},{"key":"e_1_3_2_1_37_1","first-page":"17","volume-title":"APPROX\/RANDOM","author":"Kaufman Tali","year":"2018","unstructured":"Tali Kaufman and Izhar Oppenheim . High order random walks: Beyond spectral gap . In APPROX\/RANDOM , pages 47:1\u201347: 17 , 2018 . Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. In APPROX\/RANDOM, pages 47:1\u201347:17, 2018."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0027-9"},{"key":"e_1_3_2_1_39_1","volume-title":"High-dimensional expanders from expanders. CoRR, abs\/1907.10771","author":"Liu Siqi","year":"2019","unstructured":"Siqi Liu , Sidhanth Mohanty , and Elizabeth Yang . High-dimensional expanders from expanders. CoRR, abs\/1907.10771 , 2019 . Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang. High-dimensional expanders from expanders. CoRR, abs\/1907.10771, 2019."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.06.007"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170006"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019772"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_3_2_1_45_1","volume-title":"Journal of Combinatorial Theory","author":"Mihail Milena","year":"1987","unstructured":"Milena Mihail and Umesh Vazirani . On the expansion of 0\/1 polytopes . Journal of Combinatorial Theory , 1987 . Milena Mihail and Umesh Vazirani. On the expansion of 0\/1 polytopes. Journal of Combinatorial Theory, 1987."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1526612.1526617"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3002-x"},{"key":"e_1_3_2_1_49_1","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver . Combinatorial optimization: polyhedra and efficiency , volume 24 . Springer Science & Business Media , 2003 . Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003."},{"key":"e_1_3_2_1_50_1","volume-title":"Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(4):351\u2013370","author":"Sinclair Alistair","year":"1992","unstructured":"Alistair Sinclair . Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(4):351\u2013370 , 1992 . Alistair Sinclair. Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(4):351\u2013370, 1992."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/140552"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"e_1_3_2_1_53_1","first-page":"149","volume-title":"STOC","author":"Weitz Dror","unstructured":"Dror Weitz . Counting independent sets up to the tree threshold . In STOC , pages 140\u2013 149 . ACM, 2006. Dror Weitz. Counting independent sets up to the tree threshold. In STOC, pages 140\u2013149. ACM, 2006."},{"key":"e_1_3_2_1_54_1","volume-title":"American Mathematical Soc.","author":"Wilmer EL","year":"2009","unstructured":"EL Wilmer , David A Levin , and Yuval Peres . Markov chains and mixing times . American Mathematical Soc. , Providence , 2009 . EL Wilmer, David A Levin, and Yuval Peres. Markov chains and mixing times. American Mathematical Soc., Providence, 2009."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384317","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":54,"alternative-id":["10.1145\/3357713.3384317","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384317","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}