The small-ID technique (3)

11 Jun 2021

This is the third post of a series about the small-ID techniques (also known as speed-up technique, simulation technique, gap technique, and not to be confused with the round-elimination technique). The first post is here.

In this post, we tackle the general case.

Let’s stop lying and be precise

The idea of lying to the nodes that we have used in the previous posts is good to grasp the idea of the technique, but what does it really mean? We can simply say that all the identifiers are encoded on the same number of bits $\ell$, and that the algorithm takes this size into account. Then its complexity is a function of $\ell$ and of the degree, which are two parameters that it can access locally. In general, as $\ell$ is $\log n$ (where $n$ is the size of the network), we write the complexity as a function of $n$, but here it is better to write the complexity of the algorithm as $f(\Delta)+g(\ell)$.

Computing small IDs

Just as in the previous post, we compute a coloring at some distance $d$, by building the $d$-product of the original graph, and running $L$ on that graph.

We get a $\beta (\Delta^d)^2$ coloring. This corresponds to IDs on $\ell’=2d \log \Delta + \log \beta$ bits.

Playing with the parameters

Just like in the previous post, we want to ensure that with the small-IDs, the algorithm will not look further than its $d$-neighborhood. Here this translates into:

\[2(r+f(\Delta)+g(\ell'))\leq d.\]

We cannot hope to have this technique work above $\log_{\Delta} n$, because the algorithm might see the whole graph in that time. In terms of ID size, this basically means that $g$ is at most linear in $\ell$. Let’s assume that $g$ is bounded from above by the following expresion:

\[g(\ell) \geq \frac{\epsilon \ell}{\log \Delta},\]

where $\epsilon$ is a constant to be tunes later.

Now by plugging the $\ell’$ we got, we have:

\[2\left(r+f(\Delta)+\frac{\epsilon 2d \log \Delta + \log \beta}{\log \Delta}\right)\leq d\]

Because $\log \Delta \geq 1$, it is sufficient to have:

\[2(r+f(\Delta)+\epsilon(2d+ \log \beta))\leq d.\]

That is:

\[2r+2f(\Delta)+2\epsilon\log \beta \leq d(1-4\epsilon).\]

Now to make this work, we need $d$ to contain some $f(\Delta)$, $r$ and $\log \beta$.

By choosing: $d=4r + 4f(\Delta)+\frac{1}{2}\log \beta$, and $\epsilon = \frac{1}{8}$, the inequality holds.

Conclusion

If we have an algorithm in time at most $f(\Delta)+\frac{1}{8}\log_{\Delta}n$ for some LCL, then there is an algorithm that does the same job, in time $O(f(\Delta)\log^{\ast}n)$. From a higher perspective, this means that for LCLs in bounded degree graphs, there is no problem whose complexity is between $\Theta(\log^{\ast}n)$ and $\Theta(\log n)$, i.e. there is a gap.

For a broad overview of the landscape of locality, included such gaps, check this talk by Jukka Suomela.