{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T13:59:25Z","timestamp":1769003965916,"version":"3.49.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["DUE-1819546, and CCF-2007287"],"award-info":[{"award-number":["DUE-1819546, and CCF-2007287"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:italic>n)<\/jats:italic>\n            sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using\n            <jats:italic>\n              L\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            -norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS\u201913). The non-linearity of\n            <jats:italic>\n              L\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            -norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the\n            <jats:italic>\n              L\n              <jats:sup>p<\/jats:sup>\n            <\/jats:italic>\n            -analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph\n            <jats:italic>G (n, d\/n)<\/jats:italic>\n            , where the previously known algorithms run in time\n            <jats:italic>\n              n\n              <jats:sup>O<\/jats:sup>\n            <\/jats:italic>\n            (log\n            <jats:italic>d<\/jats:italic>\n            ) or applied only to large\n            <jats:italic>d<\/jats:italic>\n            . We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant\n            <jats:italic>d<\/jats:italic>\n            , throughout the uniqueness regime.\n          <\/jats:p>","DOI":"10.1145\/3631354","type":"journal-article","created":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T11:37:36Z","timestamp":1699529856000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8966-5396","authenticated-orcid":false,"given":"Ivona","family":"Bez\u00e1kov\u00e1","sequence":"first","affiliation":[{"name":"Rochester Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3579-6531","authenticated-orcid":false,"given":"Andreas","family":"Galanis","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4849-7955","authenticated-orcid":false,"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[{"name":"University of Rochester, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,22]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384317"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520048"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00125"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0369-4"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448645"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1219722"},{"key":"e_1_3_4_8_2","first-page":"24:1\u201324:15","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201922)","volume":"245","author":"Blanca A.","year":"2022","unstructured":"A. Blanca and R. Gheissari. 2022. Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201922), Vol. 245. 24:1\u201324:15."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04237-1"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00062"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00022"},{"key":"e_1_3_4_12_2","first-page":"110","volume-title":"Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201922)","author":"Chen Y.","year":"2022","unstructured":"Y. Chen and R. Eldan. 2022. Localization schemes: A framework for proving mixing bounds for Markov chains. In Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201922). 110\u2013122."},{"key":"e_1_3_4_13_2","volume-title":"Optimal Mixing of Markov Chains for Spin Systems via Spectral Independence","author":"Chen Z.","year":"2021","unstructured":"Z. Chen. 2021. Optimal Mixing of Markov Chains for Spin Systems via Spectral Independence. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451035"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M136685X"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.22"},{"key":"e_1_3_4_18_2","first-page":"54:1\u201354:17","volume-title":"Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP\u201923)","author":"Efthymiou C.","year":"2023","unstructured":"C. Efthymiou and W. Feng. 2023. On the mixing time of glauber dynamics for the hard-core and related models on \\(G(n, d\/n)\\) . In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP\u201923). 54:1\u201354:17."},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.115"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/1387068.1387071"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20479"},{"key":"e_1_3_4_22_2","first-page":"36:1\u201336:13","volume-title":"Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201921)","author":"Galanis A.","year":"2021","unstructured":"A. Galanis, L. A. Goldberg, and J. Stewart. 2021. Fast mixing via polymers for random graphs with unbounded degree. In Proceedings of the Conference on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM\u201921). 36:1\u201336:13. Retrieved from https:\/\/arxiv.org\/abs\/2105.00524"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_3_4_24_2","unstructured":"V. Jain H. T. Pham and T. D. Vuong. 2021. Spectral independence coupling with the stationary distribution and the spectral gap of the glauber dynamics. Retrieved from https:\/\/arxiv.org\/abs\/2105.01201"},{"key":"e_1_3_4_25_2","volume-title":"Random Graphs","author":"Janson S.","year":"2011","unstructured":"S. Janson, A. Rucinski, and T. \u0141uczak. 2011. Random Graphs. John Wiley & Sons."},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_3_4_28_2","first-page":"Art. No. 4, 27","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917)","volume":"67","author":"Kaufman T.","year":"2017","unstructured":"T. Kaufman and D. Mass. 2017. High dimensional random walks and colorful expansion. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917). Vol. 67. Art. No. 4, 27."},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3847-0"},{"key":"e_1_3_4_30_2","first-page":"67","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","year":"2013","unstructured":"L.Li, P. Lu, and Y. Yin. 2013. Correlation decay up to uniqueness in spin dystems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913). 67\u201384."},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP737"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9948-x"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1541667626"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-004-2055-4"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0708-2"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.75"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.40"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631354","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3631354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:35:52Z","timestamp":1750178152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,22]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3631354"],"URL":"https:\/\/doi.org\/10.1145\/3631354","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,22]]},"assertion":[{"value":"2022-10-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-10","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}