{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:12:01Z","timestamp":1787389921962,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":20,"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":"Department of Atomic Energy, Governmanet of India","award":["12-R&D-TFR-5.01-0500"],"award-info":[{"award-number":["12-R&D-TFR-5.01-0500"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384244","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"631-642","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Improved bounds for perfect sampling of k-colorings in graphs"],"prefix":"10.1145","author":[{"given":"Siddharth","family":"Bhandari","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sayantan","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics","author":"Barvinok Alexander I.","unstructured":"Alexander I. Barvinok . 2016. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics , Vol. 30 . Springer . https:\/\/dx.doi.org\/10.1007\/ 978- Alexander I. Barvinok. 2016. Combinatorics and Complexity of Partition Functions. Algorithms and Combinatorics, Vol. 30. Springer. https:\/\/dx.doi.org\/10.1007\/ 978-"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646111"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.134"},{"key":"#cr-split#-e_1_3_2_1_4_1.1","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer Alan M. Frieze Thomas P. Hayes and Eric Vigoda. 2013. Randomly coloring constant degree graphs. Random Structures Algorithms 43 2 ( 2013 ) 181-200. https:\/\/dx.doi.org\/10.1002\/rsa.20451 (Preliminary version in 10.1002\/rsa.20451","DOI":"10.1002\/rsa.20451"},{"key":"#cr-split#-e_1_3_2_1_4_1.2","doi-asserted-by":"crossref","unstructured":"Martin E. Dyer Alan M. Frieze Thomas P. Hayes and Eric Vigoda. 2013. Randomly coloring constant degree graphs. Random Structures Algorithms 43 2 ( 2013 ) 181-200. https:\/\/dx.doi.org\/10.1002\/rsa.20451 (Preliminary version in","DOI":"10.1002\/rsa.20451"},{"key":"e_1_3_2_1_5_1","volume-title":"Perfect sampling from spatial mixing. ( 2019 ). arXiv","author":"Feng Weiming","year":"1907","unstructured":"Weiming Feng , Heng Guo , and Yitong Yin . 2019. Perfect sampling from spatial mixing. ( 2019 ). arXiv : 1907 . 06033 ( manuscript ). Weiming Feng, Heng Guo, and Yitong Yin. 2019. Perfect sampling from spatial mixing. ( 2019 ). arXiv: 1907. 06033 ( manuscript )."},{"key":"e_1_3_2_1_6_1","volume-title":"Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms 12 ( 2012 ), 29-47. arXiv:math\/0606143 https:\/\/dx.doi.org\/10.1016\/j.jda","author":"Gamarnik David","year":"2010","unstructured":"David Gamarnik and Dmitriy Katz . 2012. Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms 12 ( 2012 ), 29-47. arXiv:math\/0606143 https:\/\/dx.doi.org\/10.1016\/j.jda . 2010 . 10.002 (Preliminary version in 18th SODA , 2007 ). 10.1016\/j.jda David Gamarnik and Dmitriy Katz. 2012. Correlation decay and deterministic FPTAS for counting colorings of a graph. J. Discrete Algorithms 12 ( 2012 ), 29-47. arXiv:math\/0606143 https:\/\/dx.doi.org\/10.1016\/j.jda. 2010. 10.002 (Preliminary version in 18th SODA, 2007 )."},{"key":"e_1_3_2_1_7_1","volume-title":"Stockmeyer","author":"Garey Michael R.","year":"1976","unstructured":"Michael R. Garey , David S. Johnson , and Larry J . Stockmeyer . 1976 . Some Simplified NP-Complete Graph Problems. Theoret. Comput. Sci. 1, 3 ( 1976 ), 237-267. https:\/\/dx.doi.org\/10.1016\/ 0304-3975 ( 76 ) 90059-1 (Preliminary version in 6th Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. 1976. Some Simplified NP-Complete Graph Problems. Theoret. Comput. Sci. 1, 3 ( 1976 ), 237-267. https:\/\/dx.doi.org\/10.1016\/ 0304-3975 ( 76 ) 90059-1 (Preliminary version in 6th"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310131"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Olle Haggstrom and Karin Nelander. 1999. On Exact Simulation of Markov Random Fields Using Coupling from the Past. Scandinavian Journal of Statistics  Olle Haggstrom and Karin Nelander. 1999. On Exact Simulation of Markov Random Fields Using Coupling from the Past. Scandinavian Journal of Statistics","DOI":"10.1111\/1467-9469.00156"},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. 30th ACM Symp. on Theory of Computing (STOC). 31-40","author":"Hayes Thomas P.","year":"2015","unstructured":"Thomas P. Hayes , Juan Carlos Vera , and Eric Vigoda . 2015 . Randomly coloring Mark Huber. 1998. Exact Sampling and Approximate Counting Techniques . In Proc. 30th ACM Symp. on Theory of Computing (STOC). 31-40 . https:\/\/dx.doi.org\/ Thomas P. Hayes, Juan Carlos Vera, and Eric Vigoda. 2015. Randomly coloring Mark Huber. 1998. Exact Sampling and Approximate Counting Techniques. In Proc. 30th ACM Symp. on Theory of Computing (STOC). 31-40. https:\/\/dx.doi.org\/"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_13_1","volume-title":"Wilmer","author":"Levin David A.","year":"2017","unstructured":"David A. Levin , Yuval Peres , and Elizabeth L . Wilmer . 2017 . Markov Chains and Mixing Times (2nd ed.). Amer. Math. Soc . https:\/\/pages.uoregon.edu\/dlevin\/ David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. 2017. Markov Chains and Mixing Times (2nd ed.). Amer. Math. Soc. https:\/\/pages.uoregon.edu\/dlevin\/"},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. 60th IEEE Symp. on Foundations of Comp. Science (FOCS). 1380-1404","author":"Liu Jingcheng","year":"2019","unstructured":"Jingcheng Liu , Alistair Sinclair , and Piyush Srivastava . 2019 . A Deterministic Algorithm for Counting Colorings with 2\u0394 Colors . In Proc. 60th IEEE Symp. on Foundations of Comp. Science (FOCS). 1380-1404 . arXiv: 1906.01228 https: Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. 2019. A Deterministic Algorithm for Counting Colorings with 2\u0394 Colors. In Proc. 60th IEEE Symp. on Foundations of Comp. Science (FOCS). 1380-1404. arXiv: 1906.01228 https:"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_44"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Fabio Martinelli and Enzo Olivieri. 1994. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161 Fabio Martinelli and Enzo Olivieri. 1994. Approach to equilibrium of Glauber dynamics in the one phase region. I. The attractive case. Comm. Math. Phys. 161","DOI":"10.1007\/BF02101929"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<223::AID-RSA14>3.0.CO;2-O"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"}],"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.3384244","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":20,"alternative-id":["10.1145\/3357713.3384244","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384244","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"}}]}}