{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:48:21Z","timestamp":1782971301349,"version":"3.54.5"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217338"],"award-info":[{"award-number":["CCF-1217338"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1318294"],"award-info":[{"award-number":["CNS-1318294"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1514383"],"award-info":[{"award-number":["CCF-1514383"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1137\/17m1117537","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T18:39:12Z","timestamp":1548873552000},"page":"122-143","source":"Crossref","is-referenced-by-count":50,"title":["An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model"],"prefix":"10.1137","volume":"48","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/3060294","volume":"64","author":"Bar-Yehuda R.","year":"2017","journal-title":"J. ACM"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"atypb3","first-page":"437","author":"Barenboim L.","year":"2018","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"atypb6","first-page":"27","author":"M","year":"1983","journal-title":"New York"},{"key":"atypb7","first-page":"379","author":"Bisht T.","year":"2014","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90102-4"},{"key":"atypb10","first-page":"154","author":"Bracha G.","year":"1984","journal-title":"New York"},{"key":"atypb11","first-page":"479","author":"Brandt S.","year":"2016","journal-title":"New York"},{"key":"atypb12","first-page":"2633","author":"Chang Y.-J.","year":"2018","journal-title":"Philadelphia"},{"key":"atypb13","first-page":"445","author":"Chang Y.-J.","year":"2018","journal-title":"New York"},{"key":"atypb14","first-page":"134","author":"Chung K.-M.","year":"2014","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2897-6"},{"key":"atypb16","first-page":"355","author":"Elkin M.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb17","first-page":"340","author":"Feuilloley L.","year":"2015","journal-title":"New York"},{"key":"atypb19","first-page":"18","author":"Fischer M.","year":"2017","journal-title":"Austria"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"atypb21","first-page":"625","author":"Fraigniaud P.","year":"2016","journal-title":"Washington, DC"},{"key":"atypb22","first-page":"270","author":"Ghaffari M.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb23","first-page":"662","author":"Ghaffari M.","year":"2018","journal-title":"Washington, DC"},{"key":"atypb24","first-page":"2505","author":"Ghaffari M.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"atypb26","first-page":"401","author":"King V.","year":"2013","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0174-8"},{"key":"atypb29","first-page":"136","author":"Kothapalli K.","year":"2012","journal-title":"Germany"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.018"},{"key":"atypb37","first-page":"403","author":"Rabin M. O.","year":"1983","journal-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, Washington, DC"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1117537","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T20:11:15Z","timestamp":1551211875000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1117537"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1,3]]},"published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1117537"],"URL":"https:\/\/doi.org\/10.1137\/17m1117537","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}