{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:04Z","timestamp":1750220404000,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR project DESCARTES"},{"name":"INRIA Project GANG"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            We carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing in which all nodes execute the same algorithm in parallel, any\n            <jats:italic>construction<\/jats:italic>\n            task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result, however, holds only for distributed tasks such that the correctness of their solutions can be locally\n            <jats:italic>checked<\/jats:italic>\n            by a deterministic algorithm. In this article, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task such that the correctness of their solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm.\n          <\/jats:p>","DOI":"10.1145\/3470640","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T01:38:50Z","timestamp":1634434730000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings"],"prefix":"10.1145","volume":"8","author":[{"given":"Laurent","family":"Feuilloley","sequence":"first","affiliation":[{"name":"DII, Universidad de Chile, Santiago de Chile, Chile"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"IRIF, Universit\u00e9 de Paris and CNRS, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132557"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2670418.2670440"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12340-0_2"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2534493"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_20"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/060670511"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365555"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347173"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_3_1_13_2","first-page":"251","volume-title":"31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs)","volume":"25","author":"Cygan Marek","year":"2014","unstructured":"Marek Cygan and Tomasz Kociumaka. 2014. Constant factor approximation for capacitated k-center with outliers. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs), Vol. 25. 251\u2013262. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.251"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281114"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611478"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584058"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0211-x"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484264"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499228"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0188-x"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11164-3_9"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3301446"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04355-0_26"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2528405"},{"issue":"1","key":"e_1_3_1_27_2","first-page":"1","article-title":"Locally checkable proofs in distributed computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela. 2016. Locally checkable proofs in distributed computing. Theor. Comput. 12, 1 (2016), 1\u201333. DOI:https:\/\/doi.org\/10.4086\/toc.2016.v012a019","journal-title":"Theor. Comput."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/85271"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.06.044"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281113"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0174-8"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188882"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378540"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_27"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0070-4"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_1_42_2","article-title":"Distributed computing","volume":"5","author":"Peleg David","year":"2000","unstructured":"David Peleg. 2000. Distributed computing. SIAM Monog. Discr. Math. Applic. 5 (2000).","journal-title":"SIAM Monog. Discr. Math. Applic."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755596"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470640","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470640","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3470640"],"URL":"https:\/\/doi.org\/10.1145\/3470640","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}