New classes of distributed time complexity

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Balliu, Alkida
dc.contributor.author Hirvonen, Juho
dc.contributor.author Korhonen, Janne H.
dc.contributor.author Lempiäinen, Tuomo
dc.contributor.author Olivetti, Dennis
dc.contributor.author Suomela, Jukka
dc.date.accessioned 2018-12-10T10:22:29Z
dc.date.available 2018-12-10T10:22:29Z
dc.date.issued 2018-06-20
dc.identifier.citation Balliu , A , Lempiäinen , T , Hirvonen , J , Olivetti , D , Korhonen , J H & Suomela , J 2018 , New classes of distributed time complexity . in STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing . ASSOCIATION FOR COMPUTING MACHINERY , pp. 521-534 , Annual ACM Symposium on Theory of Computing , Los Angeles , United States , 25/06/2018 . DOI: 10.1145/3188745.3188860 en
dc.identifier.isbn 9781450355599
dc.identifier.other PURE UUID: 84d4a8b9-458a-413e-b1da-7e3e2754e385
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/new-classes-of-distributed-time-complexity(84d4a8b9-458a-413e-b1da-7e3e2754e385).html
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85049905929&partnerID=8YFLogxK
dc.identifier.other PURE LINK: https://arxiv.org/abs/1711.01871
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/31190657/SCI_Balliu_Hirvonen_et.al_New_Classes_of_Distributed_Time_Complexity.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/35134
dc.description.abstract A number of recent papers – e.g. Brandt et al. (STOC 2016), Chang et al. (FOCS 2016), Ghaffari & Su (SODA 2017), Brandt et al. (PODC 2017), and Chang & Pettie (FOCS 2017) – have advanced our understanding of one of the most fundamental questions in theory of distributed computing: what are the possible time complexity classes of LCL problems in the LOCAL model? In essence, we have a graph problem Π in which a solution can be verified by checking all radius-O(1) neighbourhoods, and the question is what is the smallest T such that a solution can be computed so that each node chooses its own output based on its radius-T neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in bounded-degree graphs that are known to exist by prior work are Θ(1), Θ(log∗ n), Θ(log n), Θ(n1/k), and Θ(n). It is also known that there are two gaps: one between ω(1) and o(log log∗ n), and another between ω(log∗ n) and o(log n). It has been conjectured that many more gapsexist, and that the overall time hierarchy is relatively simple – indeed, this is known to be the case in restricted graph families such as cycles and grids. We show that the picture is much more diverse than previously expected. We present a general technique for engineering LCL problems with numerous different deterministic time complexities, including Θ(logα n) for any α ≥ 1, 2Θ(log^α n) for any α ≤ 1, and Θ(nα) for any α < 1/2 in the high end of the complexity spectrum, and Θ(logα log∗ n) for any α ≥ 1, 2Θ(log^α log^∗ n) for any α ≤ 1, and Θ((log∗ n)α) for any α ≤ 1 in the low end of the complexity spectrum; here α is a positive rational number. en
dc.format.extent 14
dc.format.extent 521-534
dc.format.mimetype application/pdf
dc.language.iso en en
dc.relation.ispartof Annual ACM Symposium on Theory of Computing en
dc.relation.ispartofseries STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing en
dc.rights openAccess en
dc.subject.other 113 Computer and information sciences en
dc.title New classes of distributed time complexity en
dc.type A4 Artikkeli konferenssijulkaisussa fi
dc.description.version Peer reviewed en
dc.contributor.department Department of Computer Science
dc.contributor.department Albert-Ludwigs-Universität
dc.contributor.department Professorship Suomela J.
dc.subject.keyword distributed complexity theory
dc.subject.keyword graph algorithms
dc.subject.keyword locally checkable labellings
dc.subject.keyword LOCAL model
dc.subject.keyword 113 Computer and information sciences
dc.identifier.urn URN:NBN:fi:aalto-201812106149
dc.identifier.doi 10.1145/3188745.3188860
dc.type.version preprint


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account