Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions

The choice to study bounded adversaries is motivated by results in related areas, which show that computational assumptions help when the inputs may depend on the public randomness. Cohen and Naor [8] introduced the preset public coins model in the context of communication complexity. In this setting, multiple players jointly compute a function of their inputs, with the inputs being selected adversarially after the public randomness is revealed. They demonstrated that by assuming the existence of collision-resistant hash functions (CRH), communication costs can be reduced. This leads us to ask whether computational assumptions might be beneficial in our domain as well.

We emphasize that this question becomes meaningful only in settings with shared randomness. When only private coins are allowed, both bounded and unbounded adversaries can be implemented by fixing an input labeling that minimizes the success probability of the LOCAL algorithm. However, the presence of shared randomness introduces an element of unpredictability: while an unbounded adversary may adapt to it, a bounded adversary cannot anticipate or prepare for it in advance.

Sub-classes of LCL can be defined with respect to the models discussed above. Let $ϵ:\mathbb{N}\to [0,1]$ be the error probability, and $r:\mathbb{N}\to \mathbb{N}$ be the round complexity. ${\text{LCL}}_{ϵ(n)}^{\mathrm{𝗉𝗋𝗂𝗏}}[r(n)]$ is the class of all LCL problems that can be solved on $n$ vertex graphs with probability $1-ϵ(n)$ within $O(r(n))$ rounds in the private coins model.

Analogous sub-classes can be defined for the oblivious model and the preset public coins model: ${\text{LCL}}_{ϵ(n)}^{𝖮}[r(n)]$, ${\text{LCL}}_{ϵ(n)}^{𝖡}[r(n)]$ and ${\text{LCL}}_{ϵ(n)}^{𝖴}[r(n)]$. Clearly, by ignoring the preset randomness, any algorithm in the private coins model can be viewed as an algorithm in the preset public coins model (with unbounded adversaries) with the same round complexity and success rate. Moreover, by restricting the adversary, any algorithm that succeeds with probability $1-ϵ(n)$ within $r(n)$ rounds still performs at least as well against the weaker adversary.

The gap demonstrated in [5] is a separation between ${\text{LCL}}_{ϵ(n)}^{\mathrm{𝗉𝗋𝗂𝗏}}[r(n)]$ and ${\text{LCL}}_{ϵ(n)}^{𝖮}[r(n)]$, for certain choices of $ϵ(n)$ and $r(n)$. Below, we point out that the rightmost and leftmost inclusions in Eq. (1) are strict. The proofs are outlined in the Appendix of the full version [13].

As for the difference between bounded and unbounded adversaries, it becomes interesting if one is willing to make computational assumptions. That is, to assume the existence of computational tasks that cannot be solved efficiently. Our focus is on hard-on-average problems. Intuitively, we can use such a problem to pose a challenge to the adversary: if it succeeds, it can generate an input labeling that forces any LOCAL algorithm to run for many rounds; otherwise, the distributed problem is solvable in few rounds.

More formally, a problem is said to be $(T,\mu )$-hard-on-average if there exists a distribution over its instances such that a $T(\lambda )$-time probabilistic algorithm cannot solve the problem on a random instance with probability better than $\mu (\lambda )$, with $\lambda$ being the instance’s length. Throughout this work we let the solver be non-uniform (that is, have access to advice of length $\mathrm{𝗉𝗈𝗅𝗒}(\lambda )$). ¹¹1This work focuses exclusively on hardness with respect to non-uniform solvers, so we sometimes treat this aspect as implicit. Moreover, when referring to a public-coin $(T,\mu )$-hard-on-average distributional problem, we make the additional assumption that the problem remains hard even when the random bits used for sampling the instance are known.

Whenever we make a claim about distributed graph problems while relying on the existence of $(T,\mu )$-hard-on-average problems, we set $\lambda$ to be a function of $n$, the graph size. We make a distinction between problems that are subexponentially hard, and ones that are only polynomially hard (see Section 3.2 for more details). However, in both cases, we set $\lambda :=\lambda (n)$ such that $T(\lambda )$ is superpolynomial in $n$ and $\mu (\lambda )$ is negligible in $n$ (smaller than $1/p(n)$ for any polynomial $p(n)$). We study the connection between LCL problems and the existence of $(T,\mu )$-hard-on-average problems. In particular, we pose the following question:

In the preset public coins model, does the existence of public-coin
hard-on-average problems help with LCL problems?

This corresponds to a gap in the round complexity between two environments, one with adversaries that run in $\mathrm{𝗉𝗈𝗅𝗒}(n)$ time and one with computationally unbounded adversaries.

Additionally, we ask whether LCL problems in the preset public coins model that satisfy certain properties might imply the existence of intractable problems. To this end, we consider LCL problems in which the success rate changes significantly depending on the computational power of the adversary.

Assume the existence of an LCL problem that, in the preset public coins model, can be solved with a significantly higher success probability when the adversary is computationally bounded.
Does this imply any known computational assumptions?

Specifically, if the gap is large enough, can it be leveraged to construct a hard-on-average problem? Note that this is not the exact reverse of the first question, which was concerned with the round complexity, rather than with the success probability.

More concretely, the (public-coin) hard-on-average problems that we consider are from the complexity class TFNP (or its non-uniform variant TFNP/poly), which stands for total search problems that can be verified in polynomial time. A search problem is total if for every instance of the problem, there exists a solution. Apparently, this class captures the desired properties that we need from hard-on-average problems.

We note that the complexity class TFNP has been extensively studied, with much of the interest primarily due to its subclasses. A notable example is the subclass PPAD, introduced by Papadimitriou [20], which is known for being complete with respect to finding Nash equilibria (see Daskalakis, Goldberg, and Papadimitriou [9]). Moreover, average-case hardness in TFNP is known to be related to other known computational assumptions. For example, Hubácek, Naor, and Yogev [14] proved that the existence of (public-coin) hard-on-average problems in TFNP/poly (or in TFNP, under additional assumptions) is implied by hard-on-average problems in NP. Bear in mind that the latter is implied by the existence of one-way functions (OWFs), whereas it is unknown whether the converse holds.

An intriguing open question is whether a result like Theorem 10 can be derived from a gap in the round complexity rather than a gap in the failure probability. Such a result will be closer in spirit to what can be considered the inverse of Theorem 4.

From a broader perspective, we believe that the main contribution of this work is pointing out connections between the performance of distributed graph algorithms and the capabilities of a centralized algorithm (which represents the globally knowledgeable adversary). That is, we shed light on how complexity measures from the distributed and the centralized settings relate. We hope this work inspires future studies that will explore links between complexity measures that are usually associated with different areas of theoretical computer science.

Section 2 outlines the main techniques used in proving Theorems 4, 10. Section 3 contains preliminaries. An abridged description of the LCL problem $\mathrm{\Pi }$ (promised in Theorem 4) is given in Section 4. Section 5 sketches the proof of Theorem 4. Complete proofs and a thorough description of $\mathrm{\Pi }$ are available in the full version [13].

To demonstrate in a gap in round complexity between settings with and without shared randomness, [5] introduced a special family of graphs. In these graphs, shared randomness allows distant nodes to coordinate, enabling them to produce a valid output labeling in $O(\log n)$ rounds with high probability. Without shared randomness, however, $\mathrm{\Omega }(\sqrt{n})$ rounds are required. On the other hand, graphs outside the family are exempted from solving the hard task.

The graphs in the family are constructed using simpler building blocks, called tree-like structures and grid structures. Tree-like structures are subgraphs that take on the form of perfect binary trees, with additional edges that connect nodes that reside in the same layer. A grid structure of dimensions $h\times w$ is a two-dimensional lattice of $h$ rows with $w$ nodes in each. Grid structures satisfying $h\ge w$ are called vertical grid structures. A graph in the family consists of a vertical grid structure of dimensions $h\times w$, on top of which we place $w$ tree-like structures such that they are aligned with the grid’s columns. We refer to this construction as augmented grid structure (or in short, AG).

Nodes in graphs from the specified family must produce outputs where: (1) all nodes in any given row output the same bit, (2) in at least one row, the output must be equal to the input given to the rightmost node. To see why this can be described using the LCL framework, observe that requirement (1) is easily locally verifiable (with each grid node inspecting the outputs of its neighbors), and that requirement (2) can be checked with the help from the column trees. Roughly speaking, the output labeling is deemed valid if the roots output YES, grid nodes output YES either if they don’t participate in the right column or if the input equals the output, and inner tree nodes return YES if and only if at least one of their children does so. These can be verified locally, and together they imply (2). See Fig. 2 for an example.

Observe that within $O(\log n)$ rounds in the LOCAL model, the view of the nodes contains the whole tree-like structure they are part of. As such, they are able to infer the index $i\in [h]$ of the row they are located in. If shared randomness $r_{\text{pub}}\in {\{0,1\}}^{\ast }$ is available, the nodes in each row $i$ of the grid can use the $i$-th bit of $r_{\text{pub}}$ as their output. Obviously, this algorithm satisfies requirement (1). Since the party that selects the inputs of the nodes is assumed to be oblivious of the shared randomness, the probability of the output colliding with the input of the rightmost node is $\frac{1}{2}$. Over $h$ rows, the probability is at least $1-n^{-c}$ if $h\ge c\log n$ for some $c>0$. If the height of the grid is smaller than that, the use of vertical grid ensures that the width is also at most $c\log n$. This allows the nodes to learn the inputs of the entire network within $O(\log n)$ rounds.

On the other hand, if shared randomness is not available, the best the nodes can do is wait for a message from the rightmost node in their row, which takes $\mathrm{\Omega }(w)$ rounds. In a grid of width $w=\mathrm{\Omega }(\sqrt{n})$, we get the desired lower bound.

In Section 4.3 we define TM encoding structures to be grid structures that have an input labeling that represents an execution of a Turing machine. In more detail, the structure is defined with respect to a specific (one-tape) Turing machine and an input, and its main component will be a grid structure large enough for writing the whole history of the tape as part of the nodes’ labels. The horizontal axis (from right to left) is associated with time, namely, each column refers to a specific step in the execution, and the vertical axis corresponds to the tape of the machine. This is illustrated in Fig. 3 (see Fig. 7 for a concrete example).

The idea of embedding transcripts of Turing machine computations into labelings of LCL problems builds on prior work. Notably, [19] demonstrated that simulating a Turing machine can be formulated as an LCL problem. Similar techniques were used by Balliu, Brandt, Olivetti, and Suomela [3], as well as Chang [6]. In all these works, however, the nodes were required to generate the transcript of the computation themselves. Our approach takes a different direction. We assume that the input labels already contain the full transcript of the computation. The role of the nodes is reduced to simply verifying the correctness of the computation. A similar idea appears in the work of Balliu, Brandt, Chang, Olivetti, Rabie, and Suomela [2], albeit with a different underlying graph structure–a path instead of a grid. This verification can be performed locally, leveraging the fact that Turing machines are local in their nature (as the head of the machine can move only to adjacent cells). If the graph has an appropriate structure and the computation encoded in the nodes’ labels is correct, the graph can qualify as a TM encoding structure.

Thus far, we haven’t mentioned what Turing machine we aim to implement as part of our graphs. In Theorem 4 we assume the existence of a public-coin hard-on-average problem in TFNP. Let $𝒮$ be the relation that defines the search problem, and $𝒟$ be the distribution over the instances. $𝒟$ is associated with an efficient sampler $D$ that receives as input a uniformly random string and outputs an instance. Moreover, since $𝒮\in \text{TFNP}$, there is an efficient verifier $V$ that on input $(x,w)$ checks whether the pair belongs to $𝒮$. On input $(r,w)$, our Turing machine $ℳ$ samples an instance by invoking the sampler $D$ on $r$. Let $x$ be the resulting instance. It then uses $V$ to verify whether $(x,w)\in 𝒮$. If this is the case, the output is $r$. Otherwise, it returns a default string $\overrightarrow{1}$.

The leftmost column of the grid of the TM encoding structure stores the output of the machine. To set the labels of this column to some string $r$, the adversary must find a solution to the instance $x=D(r)$. The hardness of $(𝒮,𝒟)$ implies that this task should be computationally challenging when $x\sim 𝒟$ (eq., when $r$ is sampled uniformly at random).

In practice, we use a somewhat more intricate graph structure, which we refer to as small-diameter augmented TM encoding structure (SATM), defined in Section 4.6. It resembles an AG with an additional tree-like structure attached on the top of it. The technical details are omitted from this simplified exposition.

The graphs in the family $𝒢$ of hard instances that we define are not exactly the same as those in [5]. We extend their augmented grid structure (AG) with a small-diameter augmented TM encoding structure (SATM), a subgraph dedicated to simulating the execution of a Turing machine. This gadget is glued to the AG, such that its rightmost column is connected to nodes with labels that stand for the output of the Turing machine. Fig. 4 depicts such a graph along with a partial input labeling of the SATM, corresponding to an unspecified Turing machine computation. For a version that highlights the relevant structural components, see Fig. 10.

In the original problem, the inputs of the nodes in the right column play a significant role. Now, the string obtained from concatenating the inputs of the nodes in this column corresponds to the output of the Turing machine. Over the augmented grid structure, our LCL problem $\mathrm{\Pi }$ is defined mostly the same as [5]’s problem, with the difference that it now depends on the output of the Turing machine.

Above, we noted that setting the output of the machine to a string $r$ is likely to be a hard computational task whenever $r$ is sampled uniformly at random. A key observation is that the nodes have a strategy that forces $r$ to be distributed this way. This is achieved by adopting the same strategy as in [5]. That is, using $r_{\text{pub}}$ for the output. In order to win, the adversary must set the output of the Turing machine to the complement $\overline{r_{\text{pub}}}$, which is also uniformly distributed. This is the main idea behind our upper bound.

Unlike efficient adversaries, a computationally unbounded adversary should be able to solve the distributional problem. Without modifications, it could have been that the sampled instance $x$ has no solutions at all. We rule this out by requiring the problem to be total. This is necessary for proving the lower bound.

To complete the proof of the upper bound, it is crucial to ensure that $\mathrm{\Pi }$ is easy on graphs outside $𝒢$. Since membership in $𝒢$ is characterized by local constraints, any such graph $G$ must contain at least one node whose neighborhood serves as evidence for the fact that $G\notin 𝒢$. Adopting a beautiful technique demonstrated in [5], we allow the output labels to encode chains of pointers leading to violations of the local constraints. That is, nodes in erroneous components may output pointers that, when followed, eventually reach a witness of the violation. This can be viewed as a locally verifiable proof for the existence of an error.

The remaining nodes–those not participating in the pointer chains–must lie in subgraphs free of local errors. The constraints are designed so that such a subgraph is always an augmented graph structure (AG) or a small-diameter augmented TM structure (SATM).

In other words, nodes that do not belong to an AG or to a SATM can produce a proof of incorrectness, while nodes within such structures are unable to forge one. Importantly, a key feature of this output labeling is that it can be obtained in $O(\log n)$ communication rounds. We distinguish between the following cases:

• $\mathrm{■}$

  Erroneous components. The proof of incorrectness serves as a valid output labeling for our problem, so no further work is needed and the nodes may terminate.

• $\mathrm{■}$

  Valid AG and SATM structures, properly connected. Namely, the graph is a member of the hard instances family $𝒢$. This scenario was addressed earlier.

• $\mathrm{■}$

  AG without a SATM. The nodes of the AG still follow the strategy outlined earlier, but in this case $\mathrm{\Pi }$’s constraints don’t require the outputs to be related to the inputs in the right column. Clearly, no additional communication is needed.

• $\mathrm{■}$

  SATM without an AG. The problem is defined such that no further steps are required.

To summarize, for every $G\notin 𝒢$, a valid output labeling for the problem $\mathrm{\Pi }$ can be generated within $O(\log n)$ rounds, completing the proof.

Let $𝒜$ be the LOCAL algorithm that performs well against bounded adversaries. As for unbounded adversaries, there is an infinite sequence of graph sizes $\mathscr{H}={\{n_i\}}_{i=1}^{\mathrm{\infty }}$, s.t for every $n_i$ there is a “hard” $n_i$ vertex graph $G_{n_i}$ on which $𝒜$ fails with probability $1/p(n_i)$. Denote by $𝒢={\{G_n\}}_{n\in \mathbb{N}}$ a family of these graphs (for $n\notin \mathscr{H}$, use arbitrary $n$ vertex graphs).

The search problem $𝒮$ will depend on the algorithm $𝒜$, the sequence $\mathscr{H}$ and the graph family $𝒢$. The instances will be pairs of a graph size and a preset public random string $r_{\text{pub}}$. Conceptually, the problem seeks to capture the difficulty faced by the adversary that chooses the input labelings. The solver takes on the role of the adversary.

First, consider the following (flawed) attempt to define $𝒮$. A solution for an instance $(1^n,r_{\text{pub}})$, for $n$ that belongs to $\mathscr{H}$, is an input labeling $x$ that satisfies: algorithm $𝒜$ fails to generate a valid output labeling when invoked on graph $G_n\in 𝒢$ with input labeling $x$ and preset public coins $r_{\text{pub}}$ with probability that is at least an inverse polynomial. Whenever $n\notin \mathscr{H}$, we permit a trivial solution (say, $x=0^n$).

Informally, the hardness of the problem arises from the intractability of finding “bad” input labelings that make $𝒜$ fail with non-negligible probability.

The issue with this approach is that it ignores the nodes’ private coins. This implies that the verification of solutions should be randomized; however, this needs to be avoided, as we aim to devise a search problem in TFNP/poly, which means that solutions must be deterministically verifiable.

Our workaround involves sampling a collection of private coins beforehand, which will be a part of the definition of our search problem $𝒮$. Then, the fraction of samples on which the algorithm $𝒜$ fails will approximate the actual error probability. We formulate this idea through the framework of characterizing multisets. This technique has been widely used, e.g., in the works of Babai and Kimmel [1] (who introduced it) and [8]. It can be viewed as a method for describing the strategy of a randomized player while using a relatively small multiset of its outputs.

In our context, we want to succinctly characterize the way $𝒜$ behaves when the nodes may toss private coins, unknown beforehand. To this end, we prepare a polynomial-sized multiset $R_n={\{r_{\text{sec}}^{(i)}\}}_i^{l(n)}$ of strings that stand for the private coins of the nodes. On a graph $G_n\in 𝒢$, input labeling $x$ and preset public randomness $r_{\text{pub}}$, the characterizing multiset consists of the output labels of $G_n$’s nodes if $𝒜$ was invoked in this setup, with $r_{\text{sec}}^{(i)}$ being the private coins of the nodes, for all $i\in [l(n)]$.

By “characterizing”, we mean that if the nodes produce an invalid output labeling with some probability, then we want the fraction of invalid output labelings in the characterizing multiset to approximate that probability.

Let $ℛ={\{R_n\}}_{n\in \mathbb{N}}$ be the collection of multisets of private coins chosen above. The search problem $𝒮$ depends on $𝒜$, $𝒢$, $\mathscr{H}$ and $ℛ$. Now, to verify whether $((1^n,r_{\text{pub}}),x)\in 𝒮$ (for $n\in \mathscr{H}$), we compute the characterizing multiset and count how many of the resulting output labelings are invalid. If it is greater than some threshold, we accept. For $n\notin \mathscr{H}$, we accept if the solution is $0^n$.

Our goal is to leverage the fact that a bounded adversary is unlikely to generate a “bad” input, in order to argue that our search problem is hard-on-average. In LCL problems, the failure probability is defined over $r_{\text{sec}}$, $r_{\text{pub}}$, and the adversary’s coins. In contrast, for a solver of the distributional problem, it is defined only over $r_{\text{pub}}$ (and the solver’s coins). To address this inconsistency, the main technical part of the proof is a transformation from solvers of the distributional search problem to adversaries for the LCL problem $\mathrm{\Psi }$. Specifically, if the solver finds an input labeling $x$ on which inverse polynomial fraction of the multiset is invalid, then there is an adversary for $\mathrm{\Psi }$ that succeeds with inverse polynomial probability. Since we assume that no efficient adversary can cause the LOCAL algorithm $𝒜$ to fail with probability higher than $\mathrm{𝗇𝖾𝗀𝗅}(n)$, we get a contradiction. This is the core idea behind showing why our search problem $𝒮$, coupled with the uniform distribution, is hard-on-average.

The resulting search problem is non-trivial, meaning that for all $n\in \mathbb{N}$, there is a non-negligible probability that a solution exists for the uniformly sampled instance. For $n\in \mathscr{H}$, our choice of $\mathscr{H}$ implies that with at least such probability, an input labeling on which $𝒜$ fails is guaranteed to exist. As for $n\notin \mathscr{H}$, a solution exists simply due to the definition of $𝒮$. Be aware that this does not yet mean that it is a total search problem, i.e., a problem in which every instance has a solution, and an additional step (that we omit from this exposition) is required.

An undirected graph $G$ is a tuple $(V,E)$, where $V$ is the set of nodes and $E$ is the set of edges (i.e., $u,v\in V$ are connected iff $\{u,v\}\in E$). A half-edge is a pair $(v,e)$ for $v\in V$, $e\in E$, where $v\in e$. We use $x_v$ (resp. $y_v$) to denote the input (resp. output) label of node $v\in V$. $x$ (resp. $y$) stands for the concatenation of all the inputs (resp. outputs).

A network of processors is modeled as an undirected graph where the nodes can communicate only with their neighbors in synchronous rounds. In each round, messages are exchanged between pairs of nodes connected via an edge. After receiving messages from the neighbors, a node performs a local computation, at the end of which it either halts and returns its output, or determines the messages to be sent to its neighbors in the next round. Each node may toss (private) coins. That is, its strategy can be randomized.

It is common to assume that the nodes are computationally unbounded. We deviate from the original model defined by Linial [16] (see also Peleg [22]), and restrict the processors to be probabilistic $\mathrm{𝗉𝗈𝗅𝗒}(n)$-time machines.

Node $v\in V$ can toss random bits $r_{\text{sec},v}\in {\{0,1\}}^{\ast }$ (independently of the other nodes). Oftentimes, we denote by $r_{\text{sec}}$ the concentration of all the nodes’ private coins.

The nodes have access to a random string $r_{\text{pub}}$, guaranteed to be independent of the private coins. For simplicity, we assume that it is uniformly distributed. Furthermore, the adversary that selects the inputs is assumed to be oblivious to the public string. We put no restrictions on the computational power of the adversary in this case.

Unlike the oblivious model, now the shared randomness and the input are no longer independent. As the name suggests, the public coins are determined in advance, allowing the adversary to make decisions based on $r_{\text{pub}}$. This can be described as a game between the adversary and the nodes in a graph $G$ that runs a LOCAL algorithm $𝒜$, where the adversary may depend on $G$ and $𝒜$.

1. 1.

   A public string $r_{\text{pub}}$ is sampled according to the uniform distribution.

2. 2.

   After seeing $r_{\text{pub}}$ (and possibly tossing its own coins), the adversary selects an input labeling $x$ ($O(1)$ bits per node).

3. 3.

   The nodes toss their private coins $r_{\text{sec}}$.

4. 4.

   On input $x$, preset public randomness $r_{\text{pub}}$ and private randomness $r_{\text{sec}}$, the nodes in the network $G$ execute the distributed algorithm $𝒜$. In the end, they return an output labeling $y$ ($O(1)$ bits per node).

We model the adversary as an algorithm ${ℬ}_{𝒜,G}$, that may depend on the graph size $n$, the graph itself $G$ and the description of the LOCAL algorithm $𝒜$ (to be executed by the nodes). Our goal is to make a distinction between the case where ${ℬ}_{𝒜,G}$ is efficient and the case where it has unlimited computational resources.

The definition for an algorithm in the preset public coins model with unbounded adversaries is almost identical, except that the adversary ${ℬ}_{𝒜,G}$ is computationally unbounded (and may be assumed to be deterministic). The full definition is omitted from this extended abstract.

Balliu, Censor-Hillel, Maus, Olivetti, and Suomela [4] defined a set of labels for half-edges ${ℰ}^{\text{tree}}=\{𝖫,𝖱,𝖯,{\mathrm{𝖢𝗁}}_{𝖫},{\mathrm{𝖢𝗁}}_{𝖱}\}$ and a corresponding set of constraints ${𝒞}^{\text{tree}}$ (see [4, Lemma 6.6]), such that a graph equipped with such labeling satisfies ${𝒞}^{\text{tree}}$ if and only if the graph is a tree-like structure. See Fig. 5 for an illustration of the way the labels ${ℰ}^{\text{tree}}$ are used for locally verifying a tree-like structure.

[5] defined an LCL problem ${\mathrm{\Pi }}^{\text{badTree}}$, with the purpose of not only verifying whether the input labeling satisfies the constraints mentioned above, but also to provide a “proof”, accessible by all nodes, of local violations of the constraints (if there are any). In more detail:

• $\mathrm{■}$

  If ${𝒞}^{\text{tree}}$ is satisfied, then the only valid output labeling is $\perp$ (in all nodes).

• $\mathrm{■}$

  If ${𝒞}^{\text{tree}}$ doesn’t hold, there is a valid output labeling that can be interpreted as a “proof” for the graph not being tree-like (i.e., a proof of incorrectness). This is done in the form of pointers that lead to the violation.

As a result, given the output labeling of ${\mathrm{\Pi }}^{\text{badTree}}$, it is enough for a node to consider its local neighborhood in order to infer that the graph it belongs to is not tree-like. Lastly, by [5, Lemma 4.5], there is $O(\log n)$ round LOCAL algorithm for solving ${\mathrm{\Pi }}^{\text{badTree}}$.

${ℰ}^{\text{grid}}=\{𝖴,𝖣,𝖫,𝖱\}$ is a set of labels for the half-edges, and ${𝒞}^{\text{grid}}$ is a corresponding set of constraints (see [4, Lemma 6.5]). Whenever the graph of interest is a valid grid structure, there’s an assignment of labels such that the constraints are all satisfied. The opposite direction is not true, and we’ll need additional conditions to hold as well. Specifically, there must be at least one node with no incident $𝖣$ or $𝖴$ half-edges, and at least one node with no incident $𝖫$ or $𝖱$ half-edges. See Fig. 6 for an example of a valid ${ℰ}^{\text{grid}}$ labeling of a grid structure.

A vertical grid structure is a grid structure of dimensions $h\times w$ that satisfies $h\ge w$. It follows from [5, Lemma 5.6] that there exists a labeling $({𝒱}^{\text{vGrid}},{ℰ}^{\text{grid}})$ and constraints ${𝒞}^{\text{vGrid}}$ that certify whether a graph is a vertical grid structures, provided the graph also satisfies the two additional conditions mentioned above.

Let $ℳ$ be the polynomial-time Turing machine (TM) of interest. Let input be an input string. $S^{ℳ}(\text{input})$ bounds the length of tape. The runtime of $ℳ$ is exactly $T^{ℳ}(\text{input})$. At time $j\in [T^{ℳ}(\text{input})]$, the tape stores the string ${\text{TAPE}}_{\text{input}}^{ℳ}(j)$.

Suppose that the input and the output are aligned to the left end of the tape. Fill the rest of the cells with blank symbols ${\mathrm{\#}}_{𝖱}$. To illustrate, at both the beginning and the end of the execution, the tape takes on the form ${\mathrm{\#}}_{𝖫}\circ \text{str}\circ {\mathrm{\#}}_{𝖱}^{+}$, where ${\mathrm{\#}}_{𝖱}^{+}$ stands for a string of unspecified (non-zero) length of ${\mathrm{\#}}_{𝖱}$’s, and str is a string of non-blank symbols. We assume is that the machine halts only when the head is on the leftmost cell.

The TM encoding structure is a grid structure of dimensions $h\times w$ for $h\ge S^{ℳ}(\text{input})$ and $w\ge T^{ℳ}(\text{input})$. Additionally, there is an assignment of labels to the nodes such that they hold information about the computation executed by the Turing machine. Every node is given the value of a cell in the tape at some point in time, and in every column there is a node whose input label indicates that the head is stationed there. This node’s label also contains the state of the machine at that moment of the execution.

Let $ℳ$ be a Turing machine that obeys our conventions. In the full version [13] we present labels ${𝒱}^{ℳ}$ and constraints ${𝒞}^{ℳ}$ (inspired by [3]). In addition, the half-edges are equipped with the grid structure’s half-edge labels ${ℰ}^{\text{grid}}$. Then, ${𝒞}^{ℳ}$ is meant to be checked along with ${𝒞}^{\text{grid}}$. See Fig. 7 for an illustration of a valid labeling. We emphasize that the extra two conditions used for certifying grid structures are still required here.

In [5, Sec. 6.1] an LCL problem ${\mathrm{\Pi }}^{\text{badAG}}$ is defined. Valid output labelings satisfy the following conditions. First, every connected subgraph induced by the nodes with the output label $\perp$ forms an AG equipped with a suitable input labeling. On the other hand, the output labeling in subgraphs induced by the nodes with non-$\perp$ outputs consists of pointer chains that lead to the violations. Extending earlier arguments, a valid output labeling can be computed in $O(\log n)$ rounds on any $n$ vertex graph [5, Lemma 6.6].

According to [4, Lemma 6.7], there is a set of (half-edge) labels ${ℰ}^{\text{SAG}}$ and a set of constraints ${𝒞}^{\text{SAG}}$ that certifies SAGs.

We denote by ${\mathrm{\Pi }}^{\text{badSAG}}$ the LCL problem whose valid output labelings are either $\perp$ or proofs of violations of ${𝒞}^{\text{SAG}}$. I.e., if ${𝒞}^{\text{SAG}}$ holds, the output is $\perp$ all over the network. Otherwise, there’s a valid output labeling with pointer chains leading to erroneous nodes [4, Lemmas 6.9-6.11].

An LCL problem ${\mathrm{\Pi }}^{\text{badSATM}}$ is defined similarly to the previously discussed ${\mathrm{\Pi }}^{\text{badSAG}}$. Violations of ${𝒞}^{ℳ}$ can be addressed using techniques akin to those used for local structural errors in the SAG. Namely, the output labeling consists of pointer chains that lead to the errors, which may now be related to issues in the simulation of the TM. This problem can still be solved in $O(\log n)$ rounds. Further details are omitted.

The LCL problem $\mathrm{\Pi }$ is defined to be hard on a graph family $𝒢$ of hard instances. Roughly speaking, these graphs consist of two components attached to each other. One is an AG, and the other is a SATM (as in Fig. 10).

The SATM component is defined with respect to the Turing machine $ℳ$ described below. Remember that we assumed the existence of a public-coin $(T,\mu )$-hard-on-average problem in TFNP $(𝒮,𝒟)$. As $𝒟$ is given to be samplable, there is an efficient sampler $D$ for $𝒟$. The sampler is assumed to be length-preserving (i.e., $|D(r)|=|r|$). The length indicates how computationally hard is the distributional problem $(𝒮,𝒟)$: no $T(|r|)$-time solver should be capable of finding a solution for $x=D(r)$ with probability greater than $\mu (|r|)$ when given $r$ that was sampled uniformly at random. Additionally, there is a TM $V$ that on input $(x,w)$, verifies if it belongs to the relation $𝒮$. $V$ is deterministic and polynomial-time (in $|x|$). Our machine’s input is of the form $(r,w,z)$, where $r$ is a string that can be used for sampling an instance, $w$ is an alleged solution for it, and $z=\overrightarrow{0}$ is a (possibly empty) vector of zeros. $ℳ$ invokes $D$ on $r$ to obtain the instance $x$. Then, it uses $V$ to check if $(x,w)\in 𝒮$. If so (and $z=\overrightarrow{0}$), $ℳ$ outputs $r\circ 1^{|z|}$. Otherwise, it outputs $\overrightarrow{1}$.

The graphs are structured such that the rightmost column of the AG is connected to the leftmost column of the SATM. In order to set the input to the rightmost column of the AG to some string $r\circ 1^{|z|}$, the adversary must be able to find a solution to the instance $x=D(r)$. For a uniformly random $r$, $x\sim {𝒟}_{|r|}$. Assuming that $(𝒮,𝒟)$ is public-coin $(T,\mu )$-hard-on-average (for non-uniform solvers), the task of finding a solution is infeasible for any $T(|r|)$ that is superpolynomial in $n$, even when the coins $r$ are known.

$\mathrm{\Pi }$ is a combination of the problems ${\mathrm{\Pi }}^{\text{badAG}}$ and ${\mathrm{\Pi }}^{\text{badSATM}}$ (introduced earlier) with a new problem ${\mathrm{\Pi }}^{\text{hard}}$, which is supposed to be round consuming for the hard instances. On graphs that consist of two components, one in which the nodes output $\perp$ when solving ${\mathrm{\Pi }}^{\text{badAG}}$, and a second component where the nodes output $\perp$ upon solving ${\mathrm{\Pi }}^{\text{badSATM}}$, the problem $\mathrm{\Pi }$ forces the nodes to solve ${\mathrm{\Pi }}^{\text{hard}}$. On the other hand, for other output labelings for ${\mathrm{\Pi }}^{\text{badAG}}$ and ${\mathrm{\Pi }}^{\text{badSATM}}$ the nodes should be exempted from solving ${\mathrm{\Pi }}^{\text{hard}}$. In this way, we ensure that $\mathrm{\Pi }$ is promise-free.

Conceptually, ${\mathrm{\Pi }}^{\text{hard}}$ is non-trivial when solved over graphs in $𝒢$. There, the AG nodes in every row are required to output the same bit. Additionally, there must be at least one row where the output bit equals the input of the rightmost node. The formal definition of $\mathrm{\Pi }$ and related discussion appear in the full version [13].

We consider a graph $G\in 𝒢$ in which the AG is square-shaped, so its height and width are both $\mathrm{\Theta }(n^c)$ for some constant $c$. Since the adversary is unbounded, the definition of the Turing machine $ℳ$ guarantees that, by choosing suitable inputs, any output string can be produced–giving the adversary full control over $ℳ$’s output. From here, the proof proceeds similarly to [5, Thm. 8.1], with the difference that the AG’s width is only guaranteed to be $\mathrm{\Omega }(n^c)$ rather than $\mathrm{\Omega }(\sqrt{n})$. $◀$

The upper bound is established by presenting an explicit LOCAL algorithm. At a high level, the algorithm first runs the procedures promised in Sections 4.4, 4.6, which produce proofs of local violations (if there are any) in the AG and the SATM in $O(\log n)$ rounds. Next, the AG nodes explore the tree-like structures they belong to, also in $O(\log n)$ rounds.

If the height of the AG is too small (i.e., $h\le C\cdot \lambda$ for some constant $C$), the problem is solved trivially by exploring the entire network and relaying the inputs from the rightmost to the leftmost AG column. Given that the bottom grid of the AG is vertical, it can be accomplished in $O(\lambda )$ rounds.

Otherwise, nodes in the top $C\cdot \lambda$ rows use bits from $r_{\text{pub}}$, while the rest output $0$. This requires no extra communication. We analyze two cases. If the AG and the SATM are not properly connected–either one is missing or the inputs in the AG’s leftmost column and the SATM’s rightmost column are not consistent–the problem $\mathrm{\Pi }$ is defined to be solvable in $O(\log n)$ rounds. In the remaining case, where they are connected and their inputs align, the adversary must force $ℳ$’s output to be $\overline{r_{\text{pub}}}\cdot \overrightarrow{1}$ (with $|\overline{r_{\text{pub}}}|=\mathrm{\Theta }(\lambda )$), which, by assumption, it can do only with negligible probability. $◀$