Loading...
Please wait, while we are loading the content...
Sublogarithmic Distributed Algorithms for Lov\'asz Local Lemma, and the Complexity Hierarchy
| Content Provider | Paperity |
|---|---|
| Author | Ghaffari, Mohsen Fischer, Manuela |
| Abstract | Locally Checkable Labeling (LCL) problems include essentially all the classic problems of LOCAL distributed algorithms. In a recent enlightening revelation, Chang and Pettie [FOCS'17] showed that any LCL (on bounded degree graphs) that has an o(log n)-round randomized algorithm can be solved in T_(LLL)(n) rounds, which is the randomized complexity of solving (a relaxed variant of) the Lovasz Local Lemma (LLL) on bounded degree n-node graphs. Currently, the best known upper bound on T_(LLL)(n) is O(log n), by Chung, Pettie, and Su [PODC'14], while the best known lower bound is Omega(log log n), by Brandt et al. [STOC'16]. Chang and Pettie conjectured that there should be an O(log log n)-round algorithm (on bounded degree graphs). |
| Starting Page | 18:1 |
| Ending Page | 18:16 |
| File Format | HTM / HTML |
| DOI | 10.4230/LIPIcs.DISC.2017.18 |
| Journal | Leibniz International Proceedings in Informatics |
| Volume Number | 91 |
| Language | English |
| Publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| Publisher Date | 2017-10-05 |
| Access Restriction | Open |
| Subject Keyword | Distributed graph algorithms List ve Locally checkable labeling problems (lcl) Frugal coloring The lov'asz local lemma (lll) Defective coloring |
| Content Type | Text |
| Resource Type | Article |
