

Title: 
New classes of distributed time complexity 
Author(s): 
Balliu, Alkida
;
Hirvonen, Juho
;
Korhonen, Janne H.
;
Lempiäinen, Tuomo
;
Olivetti, Dennis
;
Suomela, Jukka

Date: 
20180620 
Language: 
en 
Pages: 
14 521534 
Department: 
Department of Computer Science AlbertLudwigsUniversität Professorship Suomela J. 
ISBN: 
9781450355599 
Series: 
STOC 2018  Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 
DOInumber: 
10.1145/3188745.3188860

Subject: 
113 Computer and information sciences

Keywords: 
distributed complexity theory, graph algorithms, locally checkable labellings, LOCAL model, 113 Computer and information sciences

» Show full item record


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. 521534 , Annual ACM Symposium on Theory of Computing , Los Angeles , United States , 25/06/2018 . DOI: 10.1145/3188745.3188860

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 radiusO(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 radiusT neighbourhood. Here T is the distributed time complexity of Π. The time complexity classes for deterministic algorithms in boundeddegree 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.


Permanent link to this item:
http://urn.fi/URN:NBN:fi:aalto201812106149
