Almost global problems in the LOCAL model

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

20 Citations (Scopus)
87 Downloads (Pure)

Abstract

The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the LOCAL model and locally checkable problems (LCLs) in bounded-degree graphs, the following picture emerges: - There are lots of problems with time complexities Theta(log^* n) or Theta(log n). - It is not possible to have a problem with complexity between omega(log^* n) and o(log n). - In general graphs, we can construct LCL problems with infinitely many complexities between omega(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 problems with complexities of the form Theta(n^alpha) for any rational 0 < alpha <=1/2, while for trees only complexities of the form Theta(n^{1/k}) are known. No LCL problem with complexity between omega(sqrt{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 omega(sqrt{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(sqrt{n}) in trees, while the same is not true in general graphs.
Original languageEnglish
Title of host publication32nd International Symposium on Distributed Computing (DISC 2018)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-16
Volume121
ISBN (Electronic)978-3-95977-092-7
DOIs
Publication statusPublished - 2018
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - New Orleans, United States
Duration: 15 Oct 201819 Oct 2018
Conference number: 32
http://www.disc-conference.org/wp/disc2018/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume121
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryUnited States
CityNew Orleans
Period15/10/201819/10/2018
Internet address

Keywords

  • Distributed complexity theoryDistributed complexity theory
  • Locally checkable labellings
  • LOCAL model

Fingerprint

Dive into the research topics of 'Almost global problems in the LOCAL model'. Together they form a unique fingerprint.

Cite this