{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T21:56:48Z","timestamp":1730325408294,"version":"3.28.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519999","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1431-1444","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Simple parallel algorithms for single-site dynamics"],"prefix":"10.1145","author":[{"given":"Hongyang","family":"Liu","sequence":"first","affiliation":[{"name":"Nanjing University, China"}]},{"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124312"},{"volume-title":"Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS). 185","year":"2021","author":"Anari Nima","key":"e_1_3_2_1_2_1","unstructured":"Nima Anari , Nathan Hu , Amin Saberi , and Aaron Schild . 2021 . Sampling Arborescences in Parallel . In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS). 185 , 18. Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. 2021. Sampling Arborescences in Parallel. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS). 185, 18."},{"volume-title":"Huy Tuan Pham, and Thuy-Duong Vuong","year":"2021","author":"Anari Nima","key":"e_1_3_2_1_3_1","unstructured":"Nima Anari , Vishesh Jain , Frederic Koehler , Huy Tuan Pham, and Thuy-Duong Vuong . 2021 . Entropic Independence II : Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities. ArXiv preprint, arXiv:2111.03247. Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. 2021. Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities. ArXiv preprint, arXiv:2111.03247."},{"volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). 151","year":"2020","author":"Biswas Amartya Shankha","key":"e_1_3_2_1_4_1","unstructured":"Amartya Shankha Biswas , Ronitt Rubinfeld , and Anak Yodpinyanee . 2020 . Local Access to Huge Random Objects Through Partial Sampling . In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). 151 , 27. Amartya Shankha Biswas, Ronitt Rubinfeld, and Anak Yodpinyanee. 2020. Local Access to Huge Random Objects Through Partial Sampling. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS). 151, 27."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.145"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646111"},{"key":"e_1_3_2_1_7_1","unstructured":"Xiaoyu Chen Weiming Feng Yitong Yin and Xinyuan Zhang. 2021. Optimal Mixing Time for the Ising Model in the Uniqueness Regime. ArXiv preprint arXiv:2111.03034. Xiaoyu Chen Weiming Feng Yitong Yin and Xinyuan Zhang. 2021. Optimal Mixing Time for the Ising Model in the Uniqueness Regime. ArXiv preprint arXiv:2111.03034."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Xiaoyu Chen Weiming Feng Yitong Yin and Xinyuan Zhang. 2022. Optimal mixing for two-state anti-ferromagnetic spin systems. ArXiv preprint arXiv:2203.07771. Xiaoyu Chen Weiming Feng Yitong Yin and Xinyuan Zhang. 2022. Optimal mixing for two-state anti-ferromagnetic spin systems. ArXiv preprint arXiv:2203.07771.","DOI":"10.1109\/FOCS54457.2022.00062"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451035"},{"volume-title":"Proceedings of the 31st Advances in Neural Information Processing Systems (NIPS). 32\u201341","year":"2018","author":"Daskalakis Constantinos","key":"e_1_3_2_1_10_1","unstructured":"Constantinos Daskalakis , Nishanth Dikkala , and Siddhartha Jayanti . 2018 . HOGWILD!-Gibbs can be PanAccurate . In Proceedings of the 31st Advances in Neural Information Processing Systems (NIPS). 32\u201341 . Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti. 2018. HOGWILD!-Gibbs can be PanAccurate. In Proceedings of the 31st Advances in Neural Information Processing Systems (NIPS). 32\u201341."},{"volume-title":"Proceedings of the 33rd International Conference on Machine Learning (ICML). 1567\u20131576","year":"2016","author":"Sa Christopher De","key":"e_1_3_2_1_11_1","unstructured":"Christopher De Sa , Kunle Olukotun , and Christopher R\u00e9 . 2016 . Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling . In Proceedings of the 33rd International Conference on Machine Learning (ICML). 1567\u20131576 . Christopher De Sa, Kunle Olukotun, and Christopher R\u00e9. 2016. Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling. In Proceedings of the 33rd International Conference on Machine Learning (ICML). 1567\u20131576."},{"volume-title":"Proceedings of the 28th Advances in Neural Information Processing Systems (NIPS). 3097\u20133105","year":"2015","author":"Sa Christopher De","key":"e_1_3_2_1_12_1","unstructured":"Christopher De Sa , Ce Zhang , Kunle Olukotun , and Christopher R\u00e9 . 2015 . Rapidly mixing Gibbs sampling for a class of factor graphs using hierarchy width . In Proceedings of the 28th Advances in Neural Information Processing Systems (NIPS). 3097\u20133105 . Christopher De Sa, Ce Zhang, Kunle Olukotun, and Christopher R\u00e9. 2015. Rapidly mixing Gibbs sampling for a class of factor graphs using hierarchy width. In Proceedings of the 28th Advances in Neural Information Processing Systems (NIPS). 3097\u20133105."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1115049"},{"volume-title":"Statistical physics and dynamical systems","author":"Dobrushin Roland L","key":"e_1_3_2_1_14_1","unstructured":"Roland L Dobrushin and Senya B Shlosman . 1985. Completely analytical Gibbs fields . In Statistical physics and dynamical systems . Springer , 371\u2013403. Roland L Dobrushin and Senya B Shlosman. 1985. Completely analytical Gibbs fields. In Statistical physics and dynamical systems. Springer, 371\u2013403."},{"volume-title":"Statistical physics and dynamical systems","author":"Dobrushin Roland Lvovich","key":"e_1_3_2_1_15_1","unstructured":"Roland Lvovich Dobrushin and Senya B Shlosman . 1985. Constructive criterion for the uniqueness of Gibbs field . In Statistical physics and dynamical systems . Springer , 347\u2013370. Roland Lvovich Dobrushin and Senya B Shlosman. 1985. Constructive criterion for the uniqueness of Gibbs field. In Statistical physics and dynamical systems. Springer, 347\u2013370."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AAP532"},{"key":"e_1_3_2_1_18_1","unstructured":"Ronen Eldan Frederic Koehler and Ofer Zeitouni. 2021. A spectral condition for spectral gap: fast mixing in high-temperature Ising models. Probability Theory and Related Fields 1\u201317. Ronen Eldan Frederic Koehler and Ofer Zeitouni. 2021. A spectral condition for spectral gap: fast mixing in high-temperature Ising models. Probability Theory and Related Fields 1\u201317."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469832"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.127"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087815"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1315099"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212757"},{"volume-title":"32nd International Symposium on Distributed Computing (DISC). 121","year":"2018","author":"Fischer Manuela","key":"e_1_3_2_1_24_1","unstructured":"Manuela Fischer and Mohsen Ghaffari . 2018 . A simple parallel and distributed sampling technique: Local glauber dynamics . In 32nd International Symposium on Distributed Computing (DISC). 121 , 26\u20131. Manuela Fischer and Mohsen Ghaffari. 2018. A simple parallel and distributed sampling technique: Local glauber dynamics. In 32nd International Symposium on Distributed Computing (DISC). 121, 26\u20131."},{"volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 194\u2013204","year":"2007","author":"Gerschcnfeld A","key":"e_1_3_2_1_25_1","unstructured":"A Gerschcnfeld and A Monianari . 2007 . Reconstruction for Models on Random Graphs . In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 194\u2013204 . A Gerschcnfeld and A Monianari. 2007. Reconstruction for Models on Random Graphs. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 194\u2013204."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1703954"},{"volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). 324\u2013332","year":"2011","author":"Gonzalez Joseph E","key":"e_1_3_2_1_27_1","unstructured":"Joseph E Gonzalez , Yucheng Low , Arthur Gretton , and Carlos Guestrin . 2011 . Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees . In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). 324\u2013332 . Joseph E Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin. 2011. Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS). 324\u2013332."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310131"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.6"},{"key":"e_1_3_2_1_30_1","first-page":"931","article-title":"A General Lower Bound for Mixing of Single-Site Dynamics on Graphs","author":"Hayes Thomas P.","year":"2007","unstructured":"Thomas P. Hayes and Alistair Sinclair . 2007 . A General Lower Bound for Mixing of Single-Site Dynamics on Graphs . The Annals of Applied Probability , 931 \u2013 952 . Thomas P. Hayes and Alistair Sinclair. 2007. A General Lower Bound for Mixing of Single-Site Dynamics on Graphs. The Annals of Applied Probability, 931\u2013952.","journal-title":"The Annals of Applied Probability"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2018.1429274"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Richard M Karp and Vijaya Ramachandran. 1991. Parallel algorithms for shared-memory machines. In Handbook of theoretical computer science (vol. A) algorithms and complexity. 869\u2013941. Richard M Karp and Vijaya Ramachandran. 1991. Parallel algorithms for shared-memory machines. In Handbook of theoretical computer science (vol. A) algorithms and complexity. 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"volume-title":"Wilmer","year":"2017","author":"Levin David A.","key":"e_1_3_2_1_34_1","unstructured":"David A. Levin , Yuval Peres , and Elizabeth L . Wilmer . 2017 . Markov chains and mixing times. American Mathematical Society , Providence, RI. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2017. Markov chains and mixing times. American Mathematical Society, Providence, RI."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548319000099"},{"key":"e_1_3_2_1_36_1","first-page":"125","article-title":"The beginning of the Monte Carlo method","volume":"15","author":"Metropolis Nicholas","year":"1987","unstructured":"Nicholas Metropolis . 1987 . The beginning of the Monte Carlo method . Los Alamos Science , 15 , 584 (1987), 125 \u2013 130 . Nicholas Metropolis. 1987. The beginning of the Monte Carlo method. Los Alamos Science, 15, 584 (1987), 125\u2013130.","journal-title":"Los Alamos Science"},{"volume-title":"Information, physics, and computation","author":"Mezard Marc","key":"e_1_3_2_1_37_1","unstructured":"Marc Mezard and Andrea Montanari . 2009. Information, physics, and computation . Oxford University Press . Marc Mezard and Andrea Montanari. 2009. Information, physics, and computation. Oxford University Press."},{"key":"e_1_3_2_1_38_1","unstructured":"M. Mitzenmacher and E. Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press. isbn:9781107154889 lccn:2016041654 M. Mitzenmacher and E. Upfal. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press. isbn:9781107154889 lccn:2016041654"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3268930"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP737"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.383347"},{"volume-title":"Proceedings of the 24th Advances in Neural Information Processing Systems (NIPS). 693\u2013701","year":"2011","author":"Niu Feng","key":"e_1_3_2_1_42_1","unstructured":"Feng Niu , Benjamin Recht , Christopher Re , and Stephen J Wright . 2011 . HOGWILD! a lock-free approach to parallelizing stochastic gradient descent . In Proceedings of the 24th Advances in Neural Information Processing Systems (NIPS). 693\u2013701 . Feng Niu, Benjamin Recht, Christopher Re, and Stephen J Wright. 2011. HOGWILD! a lock-free approach to parallelizing stochastic gradient descent. In Proceedings of the 24th Advances in Neural Information Processing Systems (NIPS). 693\u2013701."},{"volume-title":"Proceedings of the Second AAAI Conference on Artificial Intelligence (AAAI). 133\u2013136","year":"1982","author":"Pearl Judea","key":"e_1_3_2_1_43_1","unstructured":"Judea Pearl . 1982 . Reverend bayes on inference engines: a distributed hierarchical approach . In Proceedings of the Second AAAI Conference on Artificial Intelligence (AAAI). 133\u2013136 . Judea Pearl. 1982. Reverend bayes on inference engines: a distributed hierarchical approach. In Proceedings of the Second AAAI Conference on Artificial Intelligence (AAAI). 133\u2013136."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"e_1_3_2_1_46_1","unstructured":"D. Stoyan W.S. Kendall and J. Mecke. 1995. Stochastic Geometry and Its Applications. Wiley. isbn:9780471950998 lccn:lc95004097 D. Stoyan W.S. Kendall and J. Mecke. 1995. Stochastic Geometry and Its Applications. Wiley. isbn:9780471950998 lccn:lc95004097"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00289-U"},{"volume-title":"Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). 144\u2013154","year":"2020","author":"Terenin Alexander","key":"e_1_3_2_1_48_1","unstructured":"Alexander Terenin , Daniel Simpson , and David Draper . 2020 . Asynchronous gibbs sampling . In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). 144\u2013154 . Alexander Terenin, Daniel Simpson, and David Draper. 2020. Asynchronous gibbs sampling. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS). 144\u2013154."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T17:09:51Z","timestamp":1673456991000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":48,"alternative-id":["10.1145\/3519935.3519999","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519999","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}
