The congested clique model of distributed computing has been receiving attention as a model for densely connected distributed systems. While there has been significant progress on the side of upper bounds, we have very little in terms of lower bounds for the congested clique; indeed, it is now known that proving explicit congested clique lower bounds is as difficult as proving circuit lower bounds. In this work, we use various more traditional complexity theory tools to build a clearer picture of the complexity landscape of the congested clique: item Nondeterminism and beyond: We introduce the nondeterministic congested clique model (analogous to NP) and show that there is a natural canonical problem family that captures all problems solvable in constant time with nondeterministic algorithms. We further generalise these notions by introducing the constant-round decision hierarchy (analogous to the polynomial hierarchy). item Non-constructive lower bounds: We lift the prior non-uniform counting arguments to a general technique for proving non-constructive uniform lower bounds for the congested clique. In particular, we prove a time hierarchy theorem for the congested clique, showing that there are decision problems of essentially all complexities, both in the deterministic and nondeterministic settings. item Fine-grained complexity: We map out relationships between various natural problems in the congested clique model, arguing that a reduction-based complexity theory currently gives us a fairly good picture of the complexity landscape of the congested clique.
A number of recent papers – e.g. (STOC 2016), (FOCS 2016), Ghaffari & Su (SODA 2017), (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), Θ(logn), Θ(n1 k), and Θ(n). It is also known that there are two gaps: one between ω(1) and o(loglog* n), and another between ω(log* n) and o(logn). 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 α We show that any randomised Monte Carlo distributed algorithm for the Lovasz local lemma requires Omega(log log n) communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of d = O(1), where d is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lovasz local lemma with a running time of O(log n) rounds in bounded-degree graphs, and the best lower bound before our work was Omega(log* n) rounds [ 2014]. We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: • We present a poly log n round deterministic algorithm for (2Δ−1)·(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ − 1) · poly log Δ-edge-coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. • We show that sinkless orientation---i.e., orienting edges such that each node has at least one out-going edge---on Δ-regular graphs can be solved in O(logΔ log n) rounds randomized and in O(logΔ n) rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for Δ-coloring Δ-regular trees. • We present a randomized O(log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + e). This can be also turned into a decomposition into a(1 + e) forests when a = Ω(log n) and into a(1 + e) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin. The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math . LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is Θ(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations. Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model. Each result has a very compelling take-away message: 1. Fast @math -coloring of trees requires random bits: Building on the recent lower bounds of , we prove that the randomized complexity of @math -coloring a tree with maximum degree @math is @math , whereas its deterministic complexity is @math for any @math . This also establishes a large separation between the deterministic complexity of @math -coloring and @math -coloring trees. 2. Randomized lower bounds imply deterministic lower bounds: We prove that any deterministic algorithm for a natural class of problems that runs in @math rounds can be transformed to run in @math rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires @math time deterministically. 3. Deterministic lower bounds imply randomized lower bounds: We prove that the randomized complexity of any natural problem on instances of size @math is at least its deterministic complexity on instances of size @math . This shows that a deterministic @math lower bound for any problem implies a randomized @math lower bound. It also illustrates that the graph shattering technique is absolutely essential to the LOCAL model.