Towards Fully Automatic Distributed Lower Bounds

A particularly elegant way to prove that a problem is of the second type is through round elimination fixed points. A locally checkable problem $\mathrm{\Pi }$ is called a round elimination fixed point if $\widehat{ℛ}(\mathrm{\Pi })=\mathrm{\Pi }$, i.e., if the problem that is “one round easier” than $\mathrm{\Pi }$ is $\mathrm{\Pi }$ itself. We say that a problem $\mathrm{\Pi }$ is a non-trivial fixed point if $\mathrm{\Pi }$ is a round elimination fixed point that cannot be solved in $0$ rounds. If a problem $\mathrm{\Pi }$ is a non-trivial fixed point, existing standard techniques directly imply that $\mathrm{\Pi }$ is a hard problem, i.e., that any deterministic $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ algorithm to solve $\mathrm{\Pi }$ requires at least $\mathrm{\Omega }({\log }_{\mathrm{\Delta }}n)$ rounds and every randomized such algorithm requires at least $\mathrm{\Omega }({\log }_{\mathrm{\Delta }}\log n)$ rounds (see, e.g., [5]). Moreover, we obtain the same lower bounds for $\mathrm{\Pi }$ if $\mathrm{\Pi }$ is not a fixed point itself but can be relaxed to a non-trivial fixed point $\tilde{\mathrm{\Pi }}$. In fact, while interesting problems exist that are non-trivial fixed points themselves (see, e.g., [17]), finding a non-trivial fixed point relaxation $\tilde{\mathrm{\Pi }}$ for $\mathrm{\Pi }$ (which we may simply call a fixed point for $\mathrm{\Pi }$) is a more common way to prove lower bounds for a given problem $\mathrm{\Pi }$ (see, e.g., [2, 5, 7]). Furthermore, as shown in [5, 7], surprisingly, fixed points can also be used to prove lower bounds on the $\mathrm{\Delta }$-dependency of easy problems, i.e., problems that can be solved in time $f(\mathrm{\Delta })\cdot O({\log }^{\ast }n)$.

In order to understand the distributed complexity of locally checkable problems, we therefore need methods to find non-trivial fixed points for such problems in case such fixed points exist. We argue that, similarly to performing and analyzing round elimination, also finding new fixed points will in many cases require some automated support for searching for fixed points. Note that in general, even for a relatively simple problem $\mathrm{\Pi }$ with a small description, the smallest fixed point relaxation $\tilde{\mathrm{\Pi }}$ of $\mathrm{\Pi }$ might be much more complex and have a much larger description than the original problem $\mathrm{\Pi }$. Consider for example the $\mathrm{\Delta }$-coloring problem in $\mathrm{\Delta }$-regular graphs. While the problem itself can be described³³3For an introduction to the description of problems, see Section 1.1.3 or Section 3.2. with $\mathrm{\Delta }$ different labels and $\mathrm{\Delta }$ different node configurations (one for each possible color), the round elimination fixed point for $\mathrm{\Delta }$-coloring that has been described in [5] consists of $2^{\mathrm{\Delta }}$ different labels and $2^{\mathrm{\Delta }}-1$ different node configurations (and no smaller fixed point for $\mathrm{\Delta }$-coloring is known or suspected to exist). Finding fixed points for problems that are not as symmetric and not as well-behaved as $\mathrm{\Delta }$-coloring might quickly become infeasible when it has to be done by hand, even when using the support of existing software for performing single round elimination steps.

While the round elimination procedure is fully automatic in the sense that it gives a mechanical way to compute $\widehat{ℛ}(\mathrm{\Pi })$ as a function of $\mathrm{\Pi }$, finding fixed point relaxations is a manual process, where it is required to guess what is the right relaxation $\tilde{\mathrm{\Pi }}$ of $\mathrm{\Pi }$ and then test if $\tilde{\mathrm{\Pi }}$ is indeed a non-trivial fixed point.

One of the major open questions in the field is understanding whether one can automatically decide whether a given problem is easy or hard. Essentially, the only known way to prove that a problem is hard is producing a non-trivial fixed point relaxation of it, and it is not even known if all hard problems admit a non-trivial fixed point relaxation.

As our first main contribution, we make substantial progress on this question, by providing a method to automatically generate relaxations $\tilde{\mathrm{\Pi }}$ of a given locally checkable problem $\mathrm{\Pi }$ that are guaranteed to be fixed points under the round elimination framework. While there is no formal guarantee that the resulting problem is non-trivial (and hence that the procedure succeeded in giving a lower bound), this procedure is able to automatically derive all fixed point relaxations that have been manually obtained in the past. Moreover, we additionally show that the procedure provides novel results.

As a first direct application we get a simpler proof of a result of [5]: by applying our method to the $\mathrm{\Delta }$-coloring problem, we directly obtain the $\mathrm{\Delta }$-coloring fixed point that was presented in [5].

Not many bounds on the complexity of defective colorings are known (we discuss known bounds in the full version of this paper). An exception is the case of defective colorings with $2$ colors, which is understood. By computing an MIS (which can be done in $O(\mathrm{\Delta }+{\log }^{\ast }n)$ rounds [15]) and assigning the MIS nodes one of the colors and the remaining nodes the other color, one obtains a $(\mathrm{\Delta }-1)$-defective $2$-coloring of the graph. Interestingly, the problem becomes hard if we try to just go one step further: in [9], it was shown that computing a $(\mathrm{\Delta }-2)$-defective $2$-coloring is a hard problem. This result has been shown via a reduction from the hardness of sinkless orientation. However, this reduction is based on the construction of virtual graphs on which the defective coloring algorithm is executed in order to obtain a sinkless orientation on the original graph, and in particular the lower bounds are not proved by providing a non-trivial fixed point. As a second application of our fixed point generation method, we show the following.

This result is significant in light of the fundamental open question stated in [18, 5] asking whether, for every locally checkable problem $\mathrm{\Pi }$ that has a deterministic $\mathrm{\Omega }({\log }_{\mathrm{\Delta }}n)$ and a randomized $\mathrm{\Omega }({\log }_{\mathrm{\Delta }}\log n)$ lower bound, such a lower bound can be proven via a round elimination fixed point. The $(\mathrm{\Delta }-2)$-defective $2$-coloring problem was one of an only very small number of such problems for which previously no fixed point lower bound proof was known.

As a main application of our automatic fixed point procedure, we study the defective coloring problem with $3$ colors. From the arbdefective coloring lower bound of [5], it is known that $d$-defective $3$-coloring is hard if $3(d+1)\le \mathrm{\Delta }$ and thus if $d\le \frac{\mathrm{\Delta }}{3}-1$. In [9], it was further shown that if $d\ge \frac{2\mathrm{\Delta }-4}{3}$, $d$-defective $3$-coloring can be solved in $O(\mathrm{\Delta }+{\log }^{\ast }n)$ rounds. By using our fixed point method, we manage to partially close this gap by proving the following statement.

This in particular implies that there is no $(1+o(1))\mathrm{\Delta }/3$-defective $3$-coloring algorithm that violates those time lower bounds, thereby ruling out the possibility of using defective $3$-coloring as an approach for attacking $O(\mathrm{\Delta })$ and $(\mathrm{\Delta }+1)$-coloring in the manner outlined before Section 1.1.

We note that the fixed point that we automatically generate for this problem is highly non-trivial, and that manually proving that the fixed point that we provide is indeed a fixed point would require to perform a case analysis over hundreds of cases. For this reason, we do not manually prove that the fixed point that we provide is indeed a fixed point. Instead, we provide a way to automate this process, by reducing the problem of determining whether a problem is a fixed point to the problem of proving that certain systems of inequalities have no solution. The remaining task of showing that said systems have no solution can be performed automatically via computer tools. This automatization process provides a partial answer to Open Question 9 in [5].

For the automatic round elimination framework, a locally checkable problem on a $\mathrm{\Delta }$-regular graph $G=(V,E)$ is formalized on the bipartite graph $H$ between the nodes $V$ and the edges $E$ of $G$.⁴⁴4More generally, round elimination can be defined on biregular bipartite graphs or hypergraphs (see Section 3). That is, $H$ is obtained by adding an additional node in the middle of the edges in $E$. Each edge of $G$ is thus split into $2$ halfedges. A solution to a locally checkable problem is given by an assignment of labels from a finite alphabet $\mathrm{\Sigma }$ to all edges of $H$ (i.e., to each halfedge of $G$). The validity of a solution is given by a set of allowed node and edge configurations, where a node configuration is a multiset of labels of size $\mathrm{\Delta }$ and an edge configuration is a multiset of labels of size $2$. One step of round elimination on $G$ is done by performing two steps of round elimination on $H$ (note that one round on $G$ corresponds to two rounds on $H$). When starting from a node-centric problem $\mathrm{\Pi }$ (i.e., a problem where the nodes in $H$ corresponding to nodes in $G$ assign the labels to their incident half-edges), the first step transforms $\mathrm{\Pi }$ into an edge-centric problem ${\mathrm{\Pi }}^{\prime }$ that is exactly one round easier on $H$ and the second step transforms the problem into a node-centric problem ${\mathrm{\Pi }}^{\prime \prime }$ that is one round easier than ${\mathrm{\Pi }}^{\prime }$ on $H$ and thus one round easier than $\mathrm{\Pi }$ on $G$. The label set ${\mathrm{\Sigma }}^{\prime }$ of ${\mathrm{\Pi }}^{\prime }$ is the power set $2^{\mathrm{\Sigma }}$ of $\mathrm{\Sigma }$ and the label set ${\mathrm{\Sigma }}^{\prime \prime }$ of ${\mathrm{\Pi }}^{\prime \prime }$ is the power set of ${\mathrm{\Sigma }}^{\prime }$. The allowed edge configurations of ${\mathrm{\Pi }}^{\prime }$ are, roughly speaking, the multisets $\{{𝖫}_1,{𝖫}_2\}$ of labels ${𝖫}_1,{𝖫}_2\in {\mathrm{\Sigma }}^{\prime }=2^{\mathrm{\Sigma }}$ such that for all ${\mathrm{\ell }}_1\in {𝖫}_1$ and ${\mathrm{\ell }}_2\in {𝖫}_2$, $\{{\mathrm{\ell }}_1,{\mathrm{\ell }}_2\}$ is an allowed edge configuration of $\mathrm{\Pi }$.⁵⁵5In the formally precise definition of the set of edge configurations of ${\mathrm{\Pi }}^{\prime }$ provided in Section 3.3, we’ll refine this definition slightly. The allowed node configurations of ${\mathrm{\Pi }}^{\prime }$ are all the multisets $\{{𝖫}_1,\mathrm{\dots },{𝖫}_{\mathrm{\Delta }}\}$ of labels ${𝖫}_i\in {\mathrm{\Sigma }}^{\prime }$ (that appear in some allowed edge configuration of ${\mathrm{\Pi }}^{\prime }$) such that there exists an allowed node configuration $\{{\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_{\mathrm{\Delta }}\}$ with ${\mathrm{\ell }}_i\in {𝖫}_i$ in problem $\mathrm{\Pi }$. In the second step, ${\mathrm{\Pi }}^{\prime \prime }$ is obtained in the same way from ${\mathrm{\Pi }}^{\prime }$, but by exchanging the roles of nodes and edges. That is, in the second step, the “for all” quantifier is applied to the allowed node configurations and the “exists” quantifier is applied to the allowed edge configurations (of ${\mathrm{\Pi }}^{\prime }$).

Note that from a computational point of view, it is mainly the application of the “for all” quantifier on the edge side when going from $\mathrm{\Pi }$ to ${\mathrm{\Pi }}^{\prime }$ and even more importantly on the node side when going from ${\mathrm{\Pi }}^{\prime }$ to ${\mathrm{\Pi }}^{\prime \prime }$ that is challenging. When implemented naively, one has to iterate over all possible size-$2$ multisets of ${\mathrm{\Sigma }}^{\prime }$ in the first step and over all possible size-$\mathrm{\Delta }$ multisets of ${\mathrm{\Sigma }}^{\prime \prime }$ in the second step. While in general, the problem ${\mathrm{\Pi }}^{\prime \prime }$ that is one round easier than the original problem $\mathrm{\Pi }$ on $G$ can be doubly exponentially larger than $\mathrm{\Pi }$, for interesting problems this is often not the case. For such more well-behaved problems, the “for all” case can potentially be computed in a much more efficient way.

As our final contribution, we give a new elegant way to perform the application of the “for all” quantifier in round elimination. The method makes use of the fact that often the node and edge configurations of a problem can be represented by a relatively small number of condensed configurations. A condensed node or edge configuration is a multiset $\{S_1,\mathrm{\dots },S_k\}$ (where $k=\mathrm{\Delta }$ for nodes and $k=2$ for edges) of sets $S_1,\mathrm{\dots },S_k\subseteq \mathrm{\Sigma }$ of labels, representing the set of all configurations $\{{\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_k\}$ for which ${\mathrm{\ell }}_i\in S_i$ for all $i\in \{1,\mathrm{\dots },k\}$. We prove that the “for all” part of round elimination can be performed by a simple process that consists of steps of the following kind. In each step, we take two condensed configurations of the current problem and we combine those condensed configurations in some way to generate new condensed configurations. We then remove redundant configurations and continue until such a step cannot generate any new condensed configurations. In the end, each condensed configuration $\{S_1,\mathrm{\dots },S_k\}$ is interpreted as a multiset of labels of the new problem. We formally define the process and prove its correctness in Section 4.

Informally, we prove that each configuration of the resulting problem can be described as a binary tree, where leaf nodes are condensed configurations of the original problem, and each internal node of the tree is the configuration obtained by combining its two children.

Since our new procedure is mainly used as a tool for obtaining fixed points, we do not formally state the benefits of this new procedure. However, we informally highlight the following:

• $\mathrm{■}$

  The new procedure avoids the cost of enumerating all possible size-$\mathrm{\Delta }$ multisets of ${\mathrm{\Sigma }}^{\prime \prime }$ in the second step, and its running time only depends on the number of input configurations, output configurations, and the height of the aforementioned trees. Such trees have height at most $\mathrm{\Delta }\cdot |{\mathrm{\Sigma }}^{\prime }|$, and we observe that, for many natural problems, the height is much smaller. We thus obtain that, for many problems of interest, the running time of the new procedure is output-sensitive.

• $\mathrm{■}$

  Thanks to the new procedure, we obtain that, in order to check whether a problem is a fixed point, it is sufficient to check whether the combination of pairs of condensed configurations does not create new configurations. While this drastically reduces the time complexity of checking whether a problem is a fixed point, this also makes it much easier to prove that a problem is a fixed point. In fact, in the latter case, it is sufficient to consider two configurations at a time, instead of going through an exponential number of cases. We point out that, even if some friendly oracle gave us the fixed point for defective $3$-coloring (which we present in the full version of this paper), we believe that, without exploiting this new procedure, proving that such a problem is indeed a fixed point would not have been possible.