Projects per year
Abstract
The landscape of the distributed time complexity is nowadays wellunderstood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in boundeddegree graphs, the following picture emerges:There are lots of problems with time complexities of Θ(log ^{∗}n) or Θ(log n).It is not possible to have a problem with complexity between ω(log ^{∗}n) and o(log n).In general graphs, we can construct LCL problems with infinitely many complexities between ω(log n) and n^{o}^{(}^{1}^{)}.In trees, problems with such complexities do not exist. However, the high end of the complexity spectrum was left open by prior work. In general graphs there are LCL problems with complexities of the form Θ(n^{α}) for any rational 0 < α≤ 1 / 2 , while for trees only complexities of the form Θ(n^{1}^{/}^{k}) are known. No LCL problem with complexity between ω(n) and o(n) is known, and neither are there results that would show that such problems do not exist. We show that:In general graphs, we can construct LCL problems with infinitely many complexities between ω(n) and o(n).In trees, problems with such complexities do not exist. Put otherwise, we show that any LCL with a complexity o(n) can be solved in time O(n) in trees, while the same is not true in general graphs.
Original language  English 

Pages (fromto)  259281 
Number of pages  23 
Journal  Distributed Computing 
Volume  34 
Issue number  4 
DOIs  
Publication status  Published  Aug 2021 
MoE publication type  A1 Journal articlerefereed 
Keywords
 Distributed complexity theory
 LOCAL model
 Locally checkable labellings
Fingerprint
Dive into the research topics of 'Almost global problems in the LOCAL model'. Together they form a unique fingerprint.Projects
 1 Finished

Charting the Landscape of Distributed Time Complexity
Hirvonen, J., Purcell, C., Suomela, J., Korhonen, J., Rabie, M., Olivetti, D. & Balliu, A.
01/09/2015 → 31/08/2019
Project: Academy of Finland: Other research funding