2019/07/25 by Václav Rozhoň, Rozhoň, Václav, Mohsen Ghaffari +1 · 12 citations
Computer Science · #Complexity and Algorithms in Graphs #Privacy-Preserving Technologies in Data #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.1907.10937
We present a simple polylogarithmic-time deterministic distributed algorithm\nfor network decomposition. This improves on a celebrated 2O(\√(\log\nn))-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a\ncentral and long-standing question in distributed graph algorithms. It also\nleads to the first polylogarithmic-time deterministic distributed algorithms\nfor numerous other problems, hence resolving several well-known and decades-old\nopen problems, including Linial's question about the deterministic complexity\nof maximal independent set [FOCS'87; SICOMP'92]---which had been called the\nmost outstanding problem in the area.\n The main implication is a more general distributed derandomization theorem:\nPut together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and\nGhaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that\n
mathsfP
textit-
mathsfRLOCAL =
mathsfP
textit-
mathsfLOCAL.\nThat is, for any problem whose solution can be checked deterministically in\npolylogarithmic-time, any polylogarithmic-time randomized algorithm can be\nderandomized to a polylogarithmic-time deterministic algorithm. Informally, for\nthe standard first-order interpretation of efficiency as polylogarithmic-time,\ndistributed algorithms do not need randomness for efficiency.\n By known connections, our result leads also to substantially faster\nrandomized distributed algorithms for a number of well-studied problems\nincluding (\Δ+1)-coloring, maximal independent set, and Lov 'asz Local\nLemma, as well as massively parallel algorithms for (\Δ+1)-coloring.\n