Brief Announcement : Distributed Derandomization Revisited

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorDahal, Sameepen_US
dc.contributor.authord'Amore, Francescoen_US
dc.contributor.authorLievonen, Henriken_US
dc.contributor.authorPicavet, Timotheen_US
dc.contributor.authorSuomela, Jukkaen_US
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.contributor.departmentComputer Science Professorsen_US
dc.contributor.editorOshman, Rotemen_US
dc.date.accessioned2023-11-01T10:14:30Z
dc.date.available2023-11-01T10:14:30Z
dc.date.issued2023-10en_US
dc.description.abstractOne of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves a locally checkable labeling problem (LCL) can be derandomized with at most exponential overhead. The original proof assumes that the number of random bits is bounded by some function of the input size. We give a new, simple proof that does not make any such assumptions - it holds even if the randomized algorithm uses infinitely many bits. While at it, we also broaden the scope of the result so that it is directly applicable far beyond LCL problems.en
dc.description.versionPeer revieweden
dc.format.extent5
dc.format.extent1-5
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationDahal , S , d'Amore , F , Lievonen , H , Picavet , T & Suomela , J 2023 , Brief Announcement : Distributed Derandomization Revisited . in R Oshman (ed.) , 37th International Symposium on Distributed Computing (DISC 2023) . , 40 , Leibniz International Proceedings in Informatics (LIPIcs) , vol. 281 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-5 , International Symposium on Distributed Computing , L'Aquila , Italy , 10/10/2023 . https://doi.org/10.4230/LIPIcs.DISC.2023.40en
dc.identifier.doi10.4230/LIPIcs.DISC.2023.40en_US
dc.identifier.isbn978-3-95977-301-0
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: fa9e3e6f-de98-49d6-83ef-7aaa3d690588en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/fa9e3e6f-de98-49d6-83ef-7aaa3d690588en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85175311592&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/126102192/Brief_Announcement_-_Distributed_Derandomization_Revisited.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/124378
dc.identifier.urnURN:NBN:fi:aalto-202311016746
dc.language.isoenen
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.relation.ispartofInternational Symposium on Distributed Computingen
dc.relation.ispartofseries37th International Symposium on Distributed Computing (DISC 2023)en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs)en
dc.relation.ispartofseriesVolume 281en
dc.rightsopenAccessen
dc.titleBrief Announcement : Distributed Derandomization Revisiteden
dc.typeConference article in proceedingsfi
dc.type.versionpublishedVersion
Files