How much does randomness help with locally checkable problems?

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

11 Sitaatiot (Scopus)


Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. Vertex colorings, maximal independent sets, and maximal matchings are examples of LCLs. On the one hand, it is known that some LCLs benefit exponentially from randomness - -for example, any deterministic distributed algorithm that finds a sinkless orientation requires Θ(log n) rounds in the LOCAL model, while the randomized complexity of the problem is Θ(log log n) rounds. On the other hand, there are also many LCLs in which randomness is useless. Previously, it was not known whether there are any LCLs that benefit from randomness, but only subexponentially. We show that such problems exist: for example, there is an LCL with deterministic complexity Θ(log2 n) rounds and randomized complexity Θ(log n log log n) rounds.

OtsikkoPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
ISBN (elektroninen)9781450375825
DOI - pysyväislinkit
TilaJulkaistu - 31 heinäk. 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM Symposium on Principles of Distributed Computing - Virtual, Online, Italia
Kesto: 3 elok. 20207 elok. 2020
Konferenssinumero: 39


ConferenceACM Symposium on Principles of Distributed Computing
KaupunkiVirtual, Online


Sukella tutkimusaiheisiin 'How much does randomness help with locally checkable problems?'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä