{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T08:04:07Z","timestamp":1767773047331,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,7,25]],"date-time":"2017-07-25T00:00:00Z","timestamp":1500940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation of China (NSFC)","award":["61672275","61272081"],"award-info":[{"award-number":["61672275","61272081"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,7,25]]},"DOI":"10.1145\/3087801.3087815","type":"proceedings-article","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T17:51:38Z","timestamp":1500573098000},"page":"121-130","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["What Can be Sampled Locally?"],"prefix":"10.1145","author":[{"given":"Weiming","family":"Feng","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxin","family":"Sun","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,7,25]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Leonid Barenboim. 2016. Deterministic (\u0394+1)-coloring in sublinear (in \u0394) time in static dynamic and faulty networks. JACM 63 5 (2016) 47:1--47:22.  Leonid Barenboim. 2016. Deterministic (\u0394+1)-coloring in sublinear (in \u0394) time in static dynamic and faulty networks. JACM 63 5 (2016) 47:1--47:22.","DOI":"10.1145\/2979675"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Leonid Barenboim and Michael Elkin. 2011. Deterministic distributed vertex coloring in polylogarithmic time. JACM 58 5 (2011) 23:1--23:25.  Leonid Barenboim and Michael Elkin. 2011. Deterministic distributed vertex coloring in polylogarithmic time. JACM 58 5 (2011) 23:1--23:25.","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Leonid Barenboim Michael Elkin Seth Pettie and Johannes Schneider. 2016. The locality of distributed symmetry breaking. JACM 63 3 (2016) 20:1--20:45.  Leonid Barenboim Michael Elkin Seth Pettie and Johannes Schneider. 2016. The locality of distributed symmetry breaking. JACM 63 3 (2016) 20:1--20:45.","DOI":"10.1145\/2903137"},{"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","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032314"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1408184111"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611465"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Atish Das Sarma Danupon Nanongkai Gopal Pandurangan and Prasad Tetali. 2013. Distributed random walks. JACM 60 1 (2013) 2:1--2:31.  Atish Das Sarma Danupon Nanongkai Gopal Pandurangan and Prasad Tetali. 2013. Distributed random walks. JACM 60 1 (2013) 2:1--2:31.","DOI":"10.1145\/2432622.2432624"},{"volume-title":"ICML'16","year":"2016","author":"Sa Christopher De","key":"e_1_3_2_1_12_1"},{"volume-title":"NIPS'15","year":"2015","author":"Sa Christopher De","key":"e_1_3_2_1_13_1"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1115049"},{"volume-title":"Large Scale Nonparametric Bayesian Inference: Data Parallelisation in the Indian Buffet Process. In NIPS'09","year":"2009","author":"Doshi-Velez Finale","key":"e_1_3_2_1_15_1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000683"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009437"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.80"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.73"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Pierre Fraigniaud Amos Korman and David Peleg. 2013. Towards a complexity theory for local distributed computing. JACM 60 5 (2013) 35:1--35:26.  Pierre Fraigniaud Amos Korman and David Peleg. 2013. Towards a complexity theory for local distributed computing. JACM 60 5 (2013) 35:1--35:26.","DOI":"10.1145\/2499228"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Alan Frieze and Eric Vigoda. 2007. A Survey on the Use of Markov Chains to Randomly Sample Colourings. Oxford Lecture Series in Mathematics and its Applications 34 (2007) 53.  Alan Frieze and Eric Vigoda. 2007. A Survey on the Use of Markov Chains to Randomly Sample Colourings. Oxford Lecture Series in Mathematics and its Applications 34 (2007) 53.","DOI":"10.1093\/acprof:oso\/9780198571278.003.0004"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Andreas Galanis Daniel Stefankovic and Eric Vigoda. 2015. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. JACM 62 6 (2015) 50:1--50:60.  Andreas Galanis Daniel Stefankovic and Eric Vigoda. 2015. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. JACM 62 6 (2015) 50:1--50:60.","DOI":"10.1145\/2785964"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000401"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"volume-title":"AISTATS'11","year":"2011","author":"Gonzalez Joseph E","key":"e_1_3_2_1_27_1"},{"volume-title":"STOC'17","year":"2017","author":"Jerrum Mark","key":"e_1_3_2_1_28_1"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897533"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.6"},{"key":"e_1_3_2_1_31_1","unstructured":"Alexander E Holroyd Oded Schramm and David B Wilson. 2014. Finitary coloring. ArXiv e-prints (2014). [arxiv]1412.2725  Alexander E Holroyd Oded Schramm and David B Wilson. 2014. Finitary coloring. ArXiv e-prints (2014). [arxiv]1412.2725"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070205"},{"volume-title":"NIPS'13","year":"2013","author":"Johnson Matthew J","key":"e_1_3_2_1_33_1"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109666"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Fabian Kuhn Thomas Moscibroda and Roger Wattenhofer. 2016. Local computation: Lower and upper bounds. JACM 63 2 (2016) 17:1--17:44.  Fabian Kuhn Thomas Moscibroda and Roger Wattenhofer. 2016. Local computation: Lower and upper bounds. JACM 63 2 (2016) 17:1--17:44.","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_3_2_1_38_1","unstructured":"David Asher Levin Yuval Peres and Elizabeth Lee Wilmer. 2009. Markov chains and mixing times. American Mathematical Soc.  David Asher Levin Yuval Peres and Elizabeth Lee Wilmer. 2009. Markov chains and mixing times. American Mathematical Soc."},{"volume-title":"FOCS'87","year":"1987","author":"Linial Nathan","key":"e_1_3_2_1_39_1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_44"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"Graph colouring problems and their applications in scheduling","volume":"48","author":"Marx D\u00e1niel","year":"2004","journal-title":"Periodica Polytechnica Electrical Engineering"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Robin A Moser and G\u00e1bor Tardos. 2010. A constructive proof of the general Lov\u00e1sz Local Lemma. JACM 57 2 (2010) 11:1--11:15.  Robin A Moser and G\u00e1bor Tardos. 2010. A constructive proof of the general Lov\u00e1sz Local Lemma. JACM 57 2 (2010) 11:1--11:15.","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167149"},{"volume-title":"NIPS'07","year":"2007","author":"Newman David","key":"e_1_3_2_1_46_1"},{"volume-title":"NIPS'11","year":"2011","author":"Niu Feng","key":"e_1_3_2_1_47_1"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"volume-title":"NIPS'09","year":"2009","author":"Smyth Padhraic","key":"e_1_3_2_1_53_1"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.57.2607"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.533196"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"volume-title":"NIPS'14","year":"2014","author":"Xu Minjie","key":"e_1_3_2_1_57_1"},{"volume-title":"NIPS'09","year":"2009","author":"Yan Feng","key":"e_1_3_2_1_58_1"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939821"}],"event":{"name":"PODC '17: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Washington DC USA","acronym":"PODC '17"},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087815","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3087801.3087815","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:14Z","timestamp":1750217414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3087801.3087815"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,25]]},"references-count":59,"alternative-id":["10.1145\/3087801.3087815","10.1145\/3087801"],"URL":"https:\/\/doi.org\/10.1145\/3087801.3087815","relation":{},"subject":[],"published":{"date-parts":[[2017,7,25]]},"assertion":[{"value":"2017-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}