## 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), Θ(n^{1/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 gaps exist, 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.

Original language | English |
---|---|

Title of host publication | STOC 2018 – Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Publisher | ACM |

Pages | 1307-1318 |

Number of pages | 12 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

Publication status | Published - 20 Jun 2018 |

MoE publication type | A4 Article in a conference publication |

Event | ACM Symposium on Theory of Computing - Los Angeles, United States Duration: 25 Jun 2018 → 29 Jun 2018 Conference number: 50 http://acm-stoc.org/stoc2018/ |

### Conference

Conference | ACM Symposium on Theory of Computing |
---|---|

Abbreviated title | STOC |

Country | United States |

City | Los Angeles |

Period | 25/06/2018 → 29/06/2018 |

Internet address |

## Keywords

- distributed complexity theory
- graph algorithms
- locally checkable labellings
- LOCAL model