{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,14]],"date-time":"2026-11-14T09:38:59Z","timestamp":1794649139160,"version":"4.9.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61902241"],"award-info":[{"award-number":["61902241"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["947778"],"award-info":[{"award-number":["947778"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n                    We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [\n                    <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n                    ]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations and implies that the corresponding Glauber dynamics is rapidly mixing.\n                  <\/jats:p>\n                  <jats:p>\n                    As a concrete application, we show that Glauber dynamics for sampling proper\n                    <jats:italic>q<\/jats:italic>\n                    -colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree \u0394 provided\n                    <jats:italic>q<\/jats:italic>\n                    \u2265 (\n                    <jats:italic>\u03b1<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    +\n                    <jats:italic>\u03b4<\/jats:italic>\n                    )\u0394 where\n                    <jats:italic>\u03b1<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    \u2248 1.763 is the unique solution to\n                    <jats:italic>\u03b1<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    = exp (1\/\n                    <jats:italic>\u03b1<\/jats:italic>\n                    <jats:sup>*<\/jats:sup>\n                    ) and\n                    <jats:italic>\u03b4<\/jats:italic>\n                    \u00de 0 is any constant. This is the first efficient algorithm for sampling proper\n                    <jats:italic>q<\/jats:italic>\n                    -colourings in this regime with possibly unbounded \u0394. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson\u00a0[\n                    <jats:xref ref-type=\"bibr\">25<\/jats:xref>\n                    ].\n                  <\/jats:p>","DOI":"10.1145\/3531008","type":"journal-article","created":{"date-parts":[[2022,4,27]],"date-time":"2022-04-27T07:55:13Z","timestamp":1651046113000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Rapid Mixing from Spectral Independence beyond the Boolean Domain"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4636-1023","authenticated-orcid":false,"given":"Weiming","family":"Feng","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8199-5596","authenticated-orcid":false,"given":"Heng","family":"Guo","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9204-7794","authenticated-orcid":false,"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, Jiangsu, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9003-5706","authenticated-orcid":false,"given":"Chihao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"161","volume-title":"FOCS","author":"Abdolazimi Dorna","year":"2021","unstructured":"Dorna Abdolazimi, Kuikui Liu, and Shayan Oveis Gharan. 2021. A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings. In FOCS. IEEE, 161\u2013172."},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"1198","DOI":"10.1145\/3357713.3384317","volume-title":"STOC","author":"Alev Vedat Levi","year":"2020","unstructured":"Vedat Levi Alev and Lap Chi Lau. 2020. Improved analysis of higher order random walks and applications. In STOC. ACM, 1198\u20131211."},{"key":"e_1_3_3_4_2","unstructured":"Nima Anari Vishesh Jain Frederic Koehler Huy Tuan Pham and Thuy-Duong Vuong. 2021. Entropic Independence in High-dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-concave Polynomials and the Ising Model. Retrieved from arxiv:2106.04105."},{"key":"e_1_3_3_5_2","first-page":"1319","volume-title":"FOCS","author":"Anari Nima","year":"2020","unstructured":"Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. 2020. Spectral independence in high-dimensional expanders and applications to the hardcore model. In FOCS. IEEE, 1319\u20131330."},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1145\/3406325.3451091","volume-title":"STOC","author":"Anari Nima","year":"2021","unstructured":"Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. 2021. Log-concave polynomials IV: Approximate exchange, tight mixing times, and near-optimal sampling of forests. In STOC. ACM, 408\u2013420."},{"key":"e_1_3_3_7_2","first-page":"1","volume-title":"STOC","author":"Anari Nima","year":"2019","unstructured":"Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. 2019. Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid. In STOC. ACM, 1\u201312."},{"key":"e_1_3_3_8_2","first-page":"3670","volume-title":"SODA","author":"Blanca Antonio","year":"2022","unstructured":"Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, and Eric Vigoda. 2022. On mixing of Markov chains: Coupling, spectral independence, and entropy factorization. In SODA. SIAM, 3670\u20133692."},{"key":"e_1_3_3_9_2","first-page":"223","volume-title":"FOCS","author":"Bubley Russ","year":"1997","unstructured":"Russ Bubley and Martin Dyer. 1997. Path coupling: A technique for proving rapid mixing in Markov chains. In FOCS. IEEE, 223\u2013231."},{"key":"e_1_3_3_10_2","series-title":"Lect. Notes Stat.","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/978-1-4612-2224-8_7","volume-title":"Probability towards 2000 (New York, 1995)","author":"Chen Mu-Fa","year":"1998","unstructured":"Mu-Fa Chen. 1998. Trilogy of couplings and general formulas for lower bound of spectral gap. In Probability towards 2000 (New York, 1995). Lect. Notes Stat., Vol. 128. Springer, New York, 123\u2013136."},{"key":"e_1_3_3_11_2","first-page":"2216","volume-title":"SODA","author":"Chen Sitan","year":"2019","unstructured":"Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. 2019. Improved bounds for randomly sampling colorings via linear programming. In SODA. SIAM, 2216\u20132234."},{"key":"e_1_3_3_12_2","first-page":"137","volume-title":"FOCS","author":"Chen Xiaoyu","year":"2021","unstructured":"Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. 2021. Rapid mixing of Glauber dynamics via spectral independence for all degrees. In FOCS. IEEE, 137\u2013148."},{"key":"e_1_3_3_13_2","unstructured":"Zongchen Chen Andreas Galanis Daniel Stefankovic and Eric Vigoda. 2020. Rapid Mixing for Colorings via Spectral Independence. Retrieved from arxiv:2007.08058."},{"key":"e_1_3_3_14_2","first-page":"1307","volume-title":"FOCS","author":"Chen Zongchen","year":"2020","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2020. Rapid mixing of glauber dynamics up to uniqueness via contraction. In FOCS. IEEE, 1307\u20131318."},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"1537","DOI":"10.1145\/3406325.3451035","volume-title":"STOC","author":"Chen Zongchen","year":"2021","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2021. Optimal mixing of Glauber dynamics: Entropy factorization via high-dimensional expansion. In STOC. ACM, 1537\u20131550."},{"key":"e_1_3_3_16_2","first-page":"149","volume-title":"FOCS","author":"Chen Zongchen","year":"2021","unstructured":"Zongchen Chen, Kuikui Liu, and Eric Vigoda. 2021. Spectral independence via stability and applications to Holant-type problems. In FOCS. IEEE, 149\u2013160."},{"key":"e_1_3_3_17_2","first-page":"1358","volume-title":"FOCS","author":"Cryan Mary","year":"2019","unstructured":"Mary Cryan, Heng Guo, and Giorgos Mousa. 2019. Modified log-Sobolev inequalities for strongly log-concave distributions. In FOCS. IEEE Computer Society, 1358\u20131370."},{"key":"e_1_3_3_18_2","first-page":"974","volume-title":"FOCS","author":"Dinur Irit","year":"2017","unstructured":"Irit Dinur and Tali Kaufman. 2017. High dimensional expanders imply agreement expanders. In FOCS. IEEE Computer Society, 974\u2013985."},{"key":"e_1_3_3_19_2","first-page":"579","volume-title":"FOCS","author":"Dyer Martin E.","year":"2001","unstructured":"Martin E. Dyer and Alan M. Frieze. 2001. Randomly colouring graphs with lower bounds on girth and maximum degree. In FOCS. IEEE Computer Society, 579\u2013587."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20451"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2014.04.018"},{"key":"e_1_3_3_22_2","unstructured":"Weiming Feng Heng Guo Yitong Yin and Chihao Zhang. 2020. Rapid Mixing from Spectral Independence beyond the Boolean Domain. Retrieved from arxiv:2007.08091."},{"key":"e_1_3_3_23_2","first-page":"53","article-title":"A survey on the use of Markov chains to randomly sample colourings","volume":"34","author":"Frieze Alan M.","year":"2007","unstructured":"Alan M. Frieze and Eric Vigoda. 2007. A survey on the use of Markov chains to randomly sample colourings. Oxford Lect. Series Math. Applic. 34 (2007), 53.","journal-title":"Oxford Lect. Series Math. Applic."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2010.10.002"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20518"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445470"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3265025"},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/780542.780584","volume-title":"STOC","author":"Hayes Thomas P.","year":"2003","unstructured":"Thomas P. Hayes. 2003. Randomly coloring graphs of girth at least five. In STOC. ACM, 269\u2013278."},{"key":"e_1_3_3_29_2","first-page":"39","volume-title":"FOCS","author":"Hayes Thomas P.","year":"2006","unstructured":"Thomas P. Hayes. 2006. A simple condition implying rapid mixing of single-site dynamics on spin systems. In FOCS. IEEE Computer Society, 39\u201346."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20502"},{"key":"e_1_3_3_31_2","first-page":"618","volume-title":"FOCS","author":"Hayes Thomas P.","year":"2003","unstructured":"Thomas P. Hayes and Eric Vigoda. 2003. A non-Markovian coupling for randomly sampling colorings. In FOCS. IEEE Computer Society, 618\u2013627."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1214\/105051606000000330"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411"},{"key":"e_1_3_3_34_2","unstructured":"Vishesh Jain Huy Tuan Pham and Thuy Duong Vuong. 2021. Spectral independence coupling with the stationary distribution and the spectral gap of the Glauber dynamics. Retrieved from arxiv:2105.01201."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/1943720.1943725"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3847-0"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"e_1_3_3_40_2","first-page":"67","volume-title":"SODA","author":"Li Liang","year":"2013","unstructured":"Liang Li, Pinyan Lu, and Yitong Yin. 2013. Correlation decay up to uniqueness in spin systems. In SODA. SIAM, 67\u201384."},{"key":"e_1_3_3_41_2","first-page":"1380","volume-title":"FOCS","author":"Liu Jingcheng","year":"2019","unstructured":"Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. 2019. A deterministic algorithm for counting colorings with \\( 2 {\\Delta } \\) colors. In FOCS. IEEE Computer Society, 1380\u20131404."},{"key":"e_1_3_3_42_2","series-title":"LIPIcs","first-page":"32:1\u201332:21","volume-title":"RANDOM","author":"Liu Kuikui","year":"2021","unstructured":"Kuikui Liu. 2021. From coupling to spectral independence and blackbox comparison with the down-up walk. In RANDOM(LIPIcs, Vol. 207). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1\u201332:21."},{"key":"e_1_3_3_43_2","first-page":"639","volume-title":"RANDOM","author":"Lu Pinyan","year":"2013","unstructured":"Pinyan Lu and Yitong Yin. 2013. Improved FPTAS for multi-spin systems. In RANDOM. Springer, 639\u2013654."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702401786"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"e_1_3_3_47_2","series-title":"LIPIcs","first-page":"96:1\u201396:15","volume-title":"ICALP","author":"Shao Shuai","year":"2020","unstructured":"Shuai Shao and Yuxin Sun. 2020. Contraction: A unified perspective of correlation decay and zero-freeness of 2-spin systems. In ICALP(LIPIcs, Vol. 168). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 96:1\u201396:15."},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2006.06.004"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"e_1_3_3_50_2","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1145\/1132516.1132538","volume-title":"STOC","author":"Weitz Dror","year":"2006","unstructured":"Dror Weitz. 2006. Counting independent sets up to the tree threshold. In STOC. ACM, 140\u2013149."},{"key":"e_1_3_3_51_2","first-page":"47","volume-title":"SODA","author":"Yin Yitong","year":"2013","unstructured":"Yitong Yin and Chihao Zhang. 2013. Approximate counting via correlation decay on planar graphs. In SODA. SIAM, 47\u201366."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531008","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:09:27Z","timestamp":1750169367000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3531008"],"URL":"https:\/\/doi.org\/10.1145\/3531008","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2021-07-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-09","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}