Proof. Let \(\mathcal{A}\) be the randomized \(\mathsf{VOLUME}\) algorithm. We construct an LCA \(\mathcal{B}\) that simulates \(\mathcal{A}\) on the same query vertex. The LCA uses its shared random tape to generate the local random strings used by the \(\mathsf{VOLUME}\) algorithm: for each vertex identifier \(u\), reserve an infinite subsequence of bits on the shared tape for \(r_u\). Since vertex identifiers come from a polynomial range in \(n\), this reservation can be fixed in advance as a deterministic function of the identifier to make sure that the randomness is independent for every vertex.

During the simulation, whenever \(\mathcal{A}\) probes a vertex \(u\), the LCA probes the same vertex through its graph oracle and additionally reads the block of random bits assigned to \(u\). The \(\mathsf{VOLUME}\) access rule only restricts which probes \(\mathcal{A}\) is allowed to make; an LCA can make all of these probes as well. Therefore, the transcript of \(\mathcal{B}\) has the same distribution as the transcript of \(\mathcal{A}\) on every query and every instance. In particular, the output labels form a feasible solution with the same success probability. The number of graph-oracle probes is exactly the number of probes made by \(\mathcal{A}\), so the probe complexity is \(O(f(n))\). ◻

Proof. For each vertex \(v\), from constraint 2 of 5, its only possible in-degree in \(G'\) is from \(\mathrm{P}(v)\) if \(\mathrm{P}(v) \ne \perp\). From constraint 3 of 5, each consistent internal vertex in \(G'\) has out-degree two, while inconsistent vertices and consistent leaves have no out-neighbor. This concludes the statement. ◻

Proof. From the definition, since the maximum degree \(\Delta\) and the parameter \(k\) are constant, we know that the set of possible input and output labels has a constant size. Now we show that there is a \(\mathsf{LOCAL}\) algorithm of radius one to check whether the local constraint is satisfied for each vertex. The consistency conditions in 5 inspect only \(v\), its incident ports, and the labels of its neighbors. As a result, we can determine whether the current vertex is consistent, internal, or a leaf using input labels from the one-hop neighborhood. After that, constraints for the output label only involve the one-hop neighborhood. Hence, every constraint is checkable in radius one. ◻

Proof of 1. From [obs:vol-weaker-than-lca], the upper bound result 3 can be generalized from \(\mathsf{VOLUME}\) to LCA, while the lower bound result 4 can be generalized from LCA to \(\mathsf{VOLUME}\). As a consequence, in both models, we have a \(\Theta(\log^k n)\) randomized algorithm for \(\Pi_\mathsf{PTL}^k\) on bounded-degree graphs and a matching lower bound for bounded-degree trees. ◻

Proof. By [obs:alg-log-walk-in-G39], all vertices visited by 5 lie on a directed walk in the graph \(G'\) from 1. We first record a simple consequence of the in-degree bound in 1. Fix a vertex \(s\) and expose a walk that starts at \(s\) and, whenever it is at a consistent internal vertex, follows an independently chosen random direction in \(\{\mathsf{L},\mathsf{R}\}\). Before the walk reaches a leaf, reaches an inconsistent vertex, or returns to \(s\), two different direction sequences of length \(t\) must end at two different vertices. Indeed, if two such prefixes first meet at a vertex other than \(s\), then that vertex has two distinct in-neighbors in \(G'\), contradicting 1. Hence, for \(t\) steps, the number of direction sequences that keep the walk “alive”, meaning that all vertices traveled by the walk are consistent internal vertices, is at most \(n\), and the probability that this happens is at most \(n2^{-t}\).

Choose a sufficiently large constant \(C\). Applying the previous bound with \(t=C\log n\) shows that the walk followed by 5 lasts more than \(C\log n\) steps with probability at most \(1/(2n^3)\) before the walk arrives at a leaf, arrives at an inconsistent vertex, or finds a cycle and triggers the branch in line [line:alg-log-walk-in-cycle]. If this walk reaches a leaf or an inconsistent vertex, the algorithm stops. Otherwise, the first walk has returned to \(v\), so it has found the unique directed cycle through \(v\). The algorithm then restarts from \(v\) using the other child of \(v\) as the first step. By 1, this second walk cannot return to \(v\): the predecessor of \(v\) on the first cycle already accounts for the only possible in-neighbor of \(v\) in \(G'\). It also cannot enter a directed cycle not containing \(v\), because entering such a cycle from outside would give the entry vertex two distinct in-neighbors in \(G'\). Therefore, the second walk must end at a leaf or an inconsistent vertex.

The same counting argument, now with the first direction fixed and all later directions random, shows that this second walk has length more than \(C\log n\) with probability at most \(1/(2n^3)\) after increasing \(C\) if necessary. By a union bound, with probability at least \(1-1/n^3\), both walks considered by the algorithm have length \(O(\log n)\). The algorithm probes only the vertices on these walks, up to a constant number of additional oracle accesses needed to check consistency and read the relevant ports. Thus 5 uses \(O(\log n)\) probes and returns a path \(\pi_v\) of length \(O(\log n)\) with probability at least \(1-1/n^3\). ◻

Proof. From 5 and union bound over all vertices, with probability \(1-1/n^2\), for any consistent vertex \(v\) in the instance, 5 generates a path \(\pi_v\) of length at most \(C \log n\) using at most \(C \log n\) probes for some constant \(C\). In the following, we assume that the event happens.

Let \(T(n,h^\star)\) be the maximum possible number of probes for 6 to generate \((d(v), b_{\mathrm{out}}(v))\) for a consistent vertex \(v\) with \(h(v) = h^\star\) in an \(n\)-vertex instance. For the base case \(T(n,1)\), from constraint 5 in 5, none of the vertices in \(\pi_v\) have a new-instance child, so there is no recursion. In conclusion, the number of probes in 6 is bounded by \(C \log n\).

For \(h^\star \ge 2\), apart from the call to 5, 6 recurses on \(\mathrm{NC}(u)\) for each \(u \in \pi_v\). Constraints 4 and 5 of 5 tell us that all vertices in \(\pi_v\) have height \(h^\star\), while all their new-instance children have height \(h^\star - 1\). As a consequence, we have the following recurrence: \[T(n,h^\star)\le C\log n\cdot T(n,h^\star - 1)+C\log n,\label{eq:log-recurse}\tag{1}\] with \(T(n,1)\le C\log n\). As \(C\) is constant with respect to \(n\), solving 1 gives \(T(n,h^\star)=O(\log^{h^\star} n)\). Finally, since the maximum height of a vertex is \(k\) in \(\Pi_\mathsf{PTL}^k\), the probe complexity of 6 is \(O(\log^k n)\). ◻

Proof. Let \(a\) be the first direction taken by \(\pi_v\), so \(w=\operatorname{child}(v,a)\). After this first step, 5 follows the random direction \(\rho(u)\) at every subsequent consistent internal vertex \(u\) on \(\pi_v\). This is true whether the first direction is \(a=\rho(v)\) or the algorithm first discovers a cycle through \(v\) and then restarts with the direction \(a\ne\rho(v)\).

If \(w\) is a leaf, then running 5 on \(w\) immediately returns \((w)\), which is the desired suffix. Otherwise, \(w\) is a consistent internal vertex. Running 5 from \(w\) starts by following \(\rho(w)\), and then follows the same random directions as the run from \(v\) did after reaching \(w\) due to shared randomness across queries. Thus, the two executions trace the same directed walk unless the execution from \(w\) returns to \(w\) and triggers the branch in line [line:alg-log-walk-in-cycle]. This cannot happen along the suffix of \(\pi_v\): if some later vertex on the suffix pointed back to \(w\), then \(w\) would have two distinct in-neighbors in \(G'\), namely \(v\) and that later vertex, contradicting 1. Hence, the execution from \(w\) will never enter the branch in line [line:alg-log-walk-in-cycle], and it stops exactly at the same terminal leaf or inconsistent vertex as the execution from \(v\). Therefore its output is \(\pi_w=(w,p_1,p_2,\dots,p_\ell)\). ◻

Proof. We distinguish the different types of vertices to prove the statement. Recall the definition of \(b'\) and \(b''\) in ?? ?? .

• For inconsistent vertices, the algorithm assigns \((\perp, 0)\) to it, satisfying the constraint.

• For a leaf \(v\), \(d(v)\) is assigned \(\perp\), \(b''(v) = 0\) and \(\pi_v = (v)\). 6 collects \(b_{\mathrm{in}}(v)\) and also \(b_{\mathrm{out}}(\mathrm{NC}(v))\) when \(\mathrm{NC}(v)\) exists, so \(b_{\mathrm{out}}(v) = b_{\mathrm{in}}(v) \oplus b'(v)\), which is ?? with \(b''(v) = 0\).

• For an internal vertex \(v\), define \(w = \operatorname{child}(v,d(v))\). When \(w\) is inconsistent, we know that \(\pi_v= (v,w)\), and \((d(w), b_{\mathrm{out}}(w)) = (\perp, 0)\), meaning that \(b''(v) = 0\) and \(b_{\mathrm{out}}(v) = b_{\mathrm{in}}(v) \oplus b'(v)\); Otherwise, from 6, \(\pi_w\) is a suffix of \(\pi_v\). Compare the processes of computing the output bit between \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolvePTL}}}\nolimits\else\textrm{\mathrm{\small SolvePTL}}\fi^k(v)\) and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolvePTL}}}\nolimits\else\textrm{\mathrm{\small SolvePTL}}\fi^k(w)\), the only difference is that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolvePTL}}}\nolimits\else\textrm{\mathrm{\small SolvePTL}}\fi^k(v)\) additionally collects \(b_{\mathrm{in}}(v)\) and \(b_{\mathrm{out}}(\mathrm{NC}(v))\) if \(\mathrm{NC}(v)\) exists. As a result, \(b_{\mathrm{out}}(v) = b_{\mathrm{out}}(w) \oplus b_{\mathrm{in}}(v) \oplus b'(v)\), which is exactly ?? .

 ◻

Proof of 3. The Las Vegas algorithm given by 6 can be converted to the required Monte Carlo guarantee by [rem:las-vegas-to-monte-carlo]. The algorithm succeeds with high probability within \(O(\log^k n)\) probes according to 1 7. ◻

Proof of 4. Suppose for contradiction that there is a randomized LCA that solves \(\Pi_\mathsf{PTL}^k\) with \(o(\log^k n)\) probes and succeeds in every instance over bounded-degree trees of size at most \(n\) with probability larger than \(1/2\). According to Yao’s minimax principle, for any distribution \(\mathcal{D}\) over such instances, there is a deterministic LCA \(\mathcal{A}\) with the same probe complexity that succeeds with probability larger than \(1/2\) over \(\mathcal{D}\).

Now set \(\mathcal{D}\) to be the uniform distribution over \(\mathcal{S}_{k,n}\). For any instance \(I \in \mathcal{S}_{k,n}\), define \(V_0\) as the set of vertices probed by \(\mathcal{A}(x)\), we have \(|V_0| = o(\log^k n)\). According to condition (iii) in 8, there exists \(I'\) with \(b_I \ne b_I'\), but all inputs in \(V_0\) are the same across two instances. As \(\mathcal{A}\) is a deterministic algorithm, the transcript of \(\mathcal{A}(x)\) on \(I\) and \(I'\) will be exactly the same, so \(\mathcal{A}\) will label \(x\) the same in both instances, and one of the two solutions must be wrong according to condition (ii). Since they have the same probability weight in \(\mathcal{D}\), \(\mathcal{A}\) cannot succeed with probability larger than \(1/2\), a contradiction. ◻

Proof. We prove the lemma by induction on \(\sum_{i=1}^\ell a_i\). In the base case, the sequence is \((1)\), and condition (i) is trivial. The graph consists only of the root \(x\), and \(\mathcal{S}_{(1)}^B\) fixes \(b_{\mathrm{in}}(x)=B\). Hence every legal solution has \(b_{\mathrm{out}}(x)=B\) by ?? , proving condition (ii). Finally, in condition (iii), the set \(V_0\) is required to have size less than one, so \(V_0=\emptyset\), and the bijection between \(\mathcal{S}_{(1)}^0\) and \(\mathcal{S}_{(1)}^1\) is trivial.

Now consider a sequence \(A=\{a_1,\dots,a_\ell\}\) with \(\sum_{i=1}^\ell a_i>1\), and let \(x\) be the root of \(G_A\). Condition (i) follows from the construction of \(G_A\) and [obs:log-lower-bound-construction-property].

To prove condition (ii), fix \(B\in\{0,1\}\) and an instance \(I\in\mathcal{S}_A^B\). Let \(b'\) and \(b''\) be the auxiliary bits used to assign \(b_{\mathrm{in}}\) inputs for \(I\). If \(\mathrm{NC}(x)\ne\perp\), the \(b_{\mathrm{in}}\) input is assigned according to some instance in \(\mathcal{S}_{(a_2,\dots,a_\ell)}^{b'}\), so by the induction hypothesis applied to the subtree rooted at \(\mathrm{NC}(x)\), every solution of \(I\) has \(b_{\mathrm{out}}(\mathrm{NC}(x))=b'\). This means that the \(b'(x)\) value defined in ?? always equals the auxiliary bit \(b'\). When \(\ell = 1\), we also have \(b'(x) = 0 = b'\).

Similarly, if \(x\) is internal and \(w=\operatorname{child}(x,d(x))\), then \(w\) is the root of either the left or right copy of \(G_{(a_1-1,a_2,\dots,a_\ell)}\), and both copies have \(b_{\mathrm{in}}\) input generated from some instance in \(\mathcal{S}_{(a_1-1,a_2,\dots,a_\ell)}^{b''}\). By induction, every solution of \(I\) has \(b_{\mathrm{out}}(w)=b''\), so the \(b''(x)\) value in ?? always equals to \(b''\), too. When \(a_1 = 1\), we also have \(b''(x) = 0 = b''\).

In sum, we have \(b'(x) = b'\) and \(b''(x) = b''\). Since \(b_{\mathrm{in}}(x) = B \oplus b' \oplus b''\), ?? gives \(b_{\mathrm{out}}(x) = B\), implying (ii).

For condition (iii), fix a set \(V_0\) of size less than \(\prod_{i=1}^\ell a_i\). If \(x\notin V_0\), the bijection \(f_{V_0}\) can simply flip \(b_{\mathrm{in}}(x)\), so we suppose \(x\in V_0\). Let \(V_{\mathrm{NC}}\) be the intersection of \(V_0\) with the subtree rooted at \(\mathrm{NC}(x)\) when it exists, and \(V_{\mathrm{NC}} = \varnothing\) if \(\mathrm{NC}(x) = \perp\). Similarly define \(V_{\mathrm{LC}}\) and \(V_{\mathrm{RC}}\).

If \(\ell>1\) and \(|V_{\mathrm{NC}}|<\prod_{i=2}^\ell a_i\), applying the induction hypothesis to the subtree rooted at \(\mathrm{NC}(x)\), there is a bijection \(f_{\mathrm{NC}}\) between \(\mathcal{S}_{\{a_2,a_3,\dots,a_\ell\}}^0\) and \(\mathcal{S}_{\{a_2,a_3,\dots,a_\ell\}}^1\) that preserves the input for vertices in \(V_{\mathrm{NC}}\). Now we define the bijection \(f_{V_0}\) in the following way: For each instance \(I\), we apply the bijection \(f_{\mathrm{NC}}\) to the subtree rooted at \(\mathrm{NC}(x)\), and keep other inputs unchanged. From the induction hypothesis, \(f_{V_0}\) is a map that preserves inputs among \(V_0\). Finally, following ?? , applying \(f_{V_0}\) changes \(b'(x)\), while \(b''(x)\) and \(b_{\mathrm{in}}(x)\) are unchanged, so \(b_{\mathrm{out}}(x)\) is flipped, showing that \(f_{V_0}\) is a bijection between \(\mathcal{S}_A^0\) and \(\mathcal{S}_A^1\).

Consider the remaining case, where either \(\ell=1\), or \(|V_\mathrm{NC}| \ge \prod_{i=2}^\ell a_i\). Since \(x\in V_0\) and \(|V_0|<a_1\prod_{i=2}^\ell a_i\), we have \[|V_{\mathrm{LC}} \cup V_{\mathrm{RC}}| = |V_0 \backslash (\{x\} \cup V_{\mathrm{NC}})| = |V_0| - 1 - |V_{\mathrm{NC}}| < \prod_{i=1}^\ell a_i - 1 - \prod_{i=2}^\ell a_i < (a_1 - 1) \prod_{i=2}^\ell a_i.\] Apply the induction hypothesis to the subtrees rooted at \(\mathrm{LC}(x)\) and \(\mathrm{RC}(x)\), we know there are bijections \(f_\mathrm{LC}, f_\mathrm{RC}\) between \(\mathcal{S}_{(a_1-1,a_2,\dots,a_\ell)}^0\) and \(\mathcal{S}_{(a_1-1,a_2,\dots,a_\ell)}^1\) which preserve the input among \(V_{\mathrm{LC}}\) and \(V_{\mathrm{RC}}\), respectively. For the bijection \(f_{V_0}\) between \(\mathcal{S}_A^0\) and \(\mathcal{S}_A^1\), we apply \(f_{\mathrm{LC}}\) to the subtree rooted at \(\mathrm{LC}(x)\), apply \(f_{\mathrm{RC}}\) to the subtree rooted at \(\mathrm{RC}(x)\), and keep other inputs unchanged. From the induction hypothesis, \(f_{V_0}\) preserves inputs among \(V_0\). Finally, from ?? , applying \(f_{V_0}\) changes \(b''(x)\) regardless of the choice of \(d(x)\), while \(b'(x)\) and \(b_{\mathrm{in}}(x)\) remain unchanged, so \(b_{\mathrm{out}}(x)\) is flipped, showing that \(f_{V_0}\) is a bijection between \(\mathcal{S}_A^0\) and \(\mathcal{S}_A^1\). ◻

Proof of 8. Recall that \(k\) is a constant. Let \(q = \Theta(\log n)\) and set \(\mathcal{S}_{k,n}\) to be \(\mathcal{S}_{\{q,q,\dots,q\}}\) where the sequence has length \(k\). According to [obs:log-lower-bound-construction-property], the graph has size \(\Theta(2^{qk}) = n^{\Theta(1)}\), and the size is less than \(n\) when the constant on \(q\) is small enough. We have \(q^k=\Theta(\log^k n)\) and all three conditions in 8 follow from 9. ◻

Proof. We induct on \(c\) to prove the following claim: For all \(0 \le a \le b \le c\), there is a good ordered binary tree \(T\) with value \(a/b\). If \(a = 0\), then we can set \(T = \perp\), and we can set \(T = \bullet\) when \(a = b\), so the base case \(c=1\) is proved.

Now we assume the induction hypothesis holds for \(c-1\) and consider the statement for \(c\). We only need to consider cases where \(b=c\) and \(a \in [1,b-1]\). Let \(p=(a-1)/(b-1)\) and \(q=a/(b-1)\). We have \(0\le p < q\le 1\), and both \(p\) and \(q\) have denominators strictly smaller than \(c\). By induction hypothesis, there are two good ordered binary trees \(T_L\), \(T_R\) whose values are \(p\) and \(q\) respectively. Now we consider the tree \(T\) where the left subtree of the root is \(T_L\) while the right subtree is \(T_R\). According to 2 , \[\operatorname{val}(T) = \frac{q}{1+q-p} = \frac{\frac{a}{b-1}}{1+\frac{a}{b-1}-\frac{a-1}{b-1}} = \frac{\frac{a}{b-1}}{\frac{b}{b-1}} = \frac{a}{b}.\] It is easy to check that \(T\) is good, and this concludes the induction. ◻

Proof of 2. For every rational \(x\in(0,1]\), choose the good ordered binary tree \(T\) with \(\operatorname{val}(T)=x\), whose existence is guaranteed by 10, and apply 3 to generate an LCL with complexity in the LCA and \(\mathsf{VOLUME}\) model \(\tilde{\Theta}(n^{\operatorname{val}(T)}) = \tilde{\Theta}(n^{x})\). ◻

Proof. As \(|T|\) is a constant, the set of possible input and output labels has a constant size. Now we show that there is a \(\mathsf{LOCAL}\) algorithm of radius one to check whether the local constraint is satisfied for each vertex. The consistency conditions in 10 inspect only \(v\), its incident ports, and the labels of its neighbors. As a result, we can determine whether a vertex is consistent within one round. After that, constraints for the output label only involve the one-hop neighborhood. Hence, every constraint is checkable in radius one. ◻

Proof of 3. From [obs:vol-weaker-than-lca], the upper bound result 11 can be generalized from \(\mathsf{VOLUME}\) to LCA, while the lower bound result 12 can be generalized from LCA to \(\mathsf{VOLUME}\). As a consequence, in both models, we have a \(\tilde{O} (n^{\operatorname{val}(T)})\) randomized algorithm for \(\Pi_{\mathsf{HC}}^T\) over bounded-degree graphs and a matching lower bound for bounded-degree trees up to a polylogarithmic factor. ◻

Proof. If \(v\) is inconsistent, or if \(v\) is consistent with \(t(v)=\perp\) or \(t(v)=r_T\), then \(v\) falls into exactly one of the first three categories. It remains to consider a consistent vertex \(v\) with \(t(v)\notin\{\perp,r_T\}\). Since \(T\) is an ordered binary tree, \(t(v)\) belongs to exactly one of \(T_L\) and \(T_R\). The vertex \(v\) is therefore included in \(V_I\) and lies in a unique connected component of \(G_I\).

We now show that this component cannot contain types from both \(T_L\) and \(T_R\). Consider an edge \(\{x,y\}\) of \(G_I\). By the definition of \(G_I\), \(x\) and \(y\) are consistent vertices, so up to swapping \(x\) and \(y\), we have \(y=\mathrm{P}(x)\) and \(x\in\{\mathrm{LC}(y),\mathrm{RC}(y),\mathrm{DC}(y)\}\). If \(x=\mathrm{DC}(y)\), then \(t(x)=t(y)\). If \(x=\mathrm{LC}(y)\) or \(x=\mathrm{RC}(y)\), then \(t(x)\) is a child of \(t(y)\) in \(T\). In all cases, as \(x,y\in V_I\), the two types lie in the same one of the two subtrees \(T_L\) and \(T_R\). Hence every connected component of \(G_I\) is contained entirely in one side, and \(v\) belongs to exactly one \(\Pi_{\mathsf{HC}}^{T_L}\) or \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instance. ◻

Proof of 11. Apply 4 with \(N_1=N_2=n^\star=n\). By conditions (ii) and (iii) of 13, the output labeling \(\{a_{u,n,n}\}_{u \in I}\) satisfies \(\Pi_{\mathsf{HC}}^T\) with probability at least \(1-1/n\). By condition (iv), the probe complexity is \(\tilde{O}(n^{\operatorname{val}(T)})\) with probability \(1 - 1/n\). Finally, we can use [rem:las-vegas-to-monte-carlo] to translate this algorithm from Las Vegas to Monte Carlo. ◻

Proof. The algorithm checks whether the queried vertex \(u\) is consistent using 10. If \(u\) is inconsistent, it is labeled \((\perp,0)\); otherwise it is labeled \((\mathsf{X},0)\). The output is not \((\mathsf{D}, 0)\) and is independent of the parameter \(N_2\), so condition (i) of 13 is satisfied.

Since \(T=\perp\), every consistent vertex has type \(\perp\). Thus \(\mathsf{X}\) is allowed by item 3(a) in the \(c_{\mathrm{out}}\) constraint, and item 3(b) is always satisfied since output color \(\mathsf{D}\) does not appear in the instance. This shows that all vertices satisfy the \(\Pi_{\mathsf{HC}}^T\) constraints on \(c_{\mathrm{out}}\). The constraint on \(b_{\mathrm{out}}\) enforces every vertex \(u\) in the instance to have \(b_{\mathrm{out}}(u)=0\). This means that conditions (ii) and (iii) hold. Finally, the probe complexity is \(O(1)\), satisfying condition (iv). ◻

Proof. The algorithm first performs the same consistency and type-\(\perp\) checks as in 14. Thus inconsistent vertices output \((\perp,0)\), type-\(\perp\) consistent vertices output \((\mathsf{X},0)\), and constraints on these vertices are satisfied. Now suppose \(u\) is consistent and \(t(u)=r_T\), then colors \(\mathsf{X}\) and \(\mathsf{D}\) are both prohibited at \(u\). With the input parameter \(N_2\), the algorithm follows the \(\mathrm{DC}\) path from \(u\) (i.e. the path \(u, \mathrm{DC}(u), \mathrm{DC}(\mathrm{DC}(u)) \dots\)) for \(N_2\) steps and outputs the first applicable label below:

• If the walk revisits \(u\), \(u\) is labeled \((\mathsf{Cyc},0)\).

• If the walk reaches a consistent vertex \(w\) such that \(\mathrm{DC}(w)=\perp\) or \(\mathrm{DC}(w)\) is inconsistent, \(u\) is labeled \(\left(\mathsf{U},\bigoplus_{z\in P_{u,w}} b_{\mathrm{in}}(z)\right)\), where \(P_{u,w}\) is the \(\mathrm{DC}\) path from \(u\) to \(w\).

• If neither event above is found within \(N_2\) steps, \(u\) is labeled \((\mathsf{D},0)\).

Now we check the conditions for strong algorithms. For a fixed \(N_1\), the threshold \(N_2^\star(u, N_1)\) is the smallest value \(N_2\) for which the walk from \(u\) sees one of the two terminating events, hence condition (i) holds.

Now we check conditions (ii) and (iii). Fix \(N_2\ge N_1\), and distinguish different possibilities for a vertex \(u\) in the instance. Inconsistent vertices and consistent type-\(\perp\) vertices have already been handled. Let \(u\) be a consistent vertex with \(t(u)=r_T\). If the algorithm outputs \((\mathsf{D},0)\), then the only possible violation is item 4 in the constraint on \(c_{\mathrm{out}}\), which is precisely the exception allowed in condition (ii).

Suppose the algorithm outputs \((\mathsf{Cyc},0)\) at \(u\). Then the \(\mathrm{DC}\) walk from \(u\) returns to \(u\) within \(N_2\) steps. For every vertex \(z\) on this directed cycle, the same walk starting from \(z\) also returns to \(z\) within \(N_2\) steps before encountering any terminating event, so \(z\) is also labeled \((\mathsf{Cyc},0)\). Hence item 1 in the constraint on \(c_{\mathrm{out}}\) is satisfied at \(u\), and the bit constraint is satisfied because vertices of color \(\mathsf{Cyc}\) have output bit zero.

Finally, suppose the algorithm outputs \(\left(\mathsf{U},\bigoplus_{z\in P_{u,w}}b_{\mathrm{in}}(z)\right)\) at \(u\), where \(w\) is the first consistent vertex on the \(\mathrm{DC}\) path from \(u\) such that \(\mathrm{DC}(w)=\perp\) or \(\mathrm{DC}(w)\) is inconsistent. If \(u=w\), then item 2 in the constraint on \(c_{\mathrm{out}}\) is immediate. Otherwise, the vertex \(\mathrm{DC}(u)\) reaches the same terminating vertex \(w\) within fewer steps, so it is also labeled \(\mathsf{U}\). Thus item 2 is satisfied at \(u\). Since \(T=\bullet\), vertices of type \(r_T\) have left and right children of type \(\perp\) whose output bit must be zero. As a result, ?? reduces to \[b_{\mathrm{out}}(u)=b_{\mathrm{in}}(u)\oplus b_{\mathrm{out}}(\mathrm{DC}(u)),\] with \(b_{\mathrm{out}}(\mathrm{DC}(u))=0\) when \(\mathrm{DC}(u)=\perp\) or \(\mathrm{DC}(u)\) is inconsistent. The bit given by the algorithm is exactly this recurrence expanded along the path from \(u\) to \(w\).

To prove condition (iii), let \(N_2\ge\max(N_1,n^\star)\) and \(u\) be a consistent vertex with \(t(u)=r_T\). Along the \(\mathrm{DC}\) walk from \(u\), the first repeated consistent vertex must be \(u\): if the first repeated vertex were \(z\ne u\), then \(z\) would have two different predecessors, contradicting the consistency definition in 10. Therefore, within at most \(n^\star\) steps, the walk either returns to \(u\) or reaches a vertex whose \(\mathrm{DC}\) port is \(\perp\) or points to an inconsistent vertex. Since \(N_2\ge n^\star\), the algorithm sees one of these terminating events and does not output \((\mathsf{D},0)\).

Finally, the walk uses \(O(\min(n^\star, N_2))\) probes for every vertex. This is \(O(N_2)\) for all vertices and \(O(\max(N_1,n^\star))\) for root-type vertices. Since \(\alpha = 1\) and \(d_T = 0\), condition (iv) holds. ◻

Proof. The behavior of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N)\) before entering the if-block in line [line:alg-poly-traverse-check-terminate] is independent of \(N\), and the sampling probability is also independent of \(N\). Hence it is enough to analyze the single random sample set on the first \(\lceil 2N_1^\beta\rceil+1\) positions of the \(\mathrm{DC}\) walk from \(u\), and all \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u, N_1, N)\) calls will give the same sampling set.

Let \(\delta = \min(1,4N_1^{-\beta}\log n)\) be the sampling probability. If \(\delta=1\), then \(N_1^\beta=O(\log n)\), so the sample set has size \(O(\log n)\). Suppose now that \(\delta<1\). We have \(\mathbb{E}[|S|] = (\lceil 2N_1^\beta\rceil+1)(4N_1^{-\beta}\log n) = \Theta(\log n),\) and a Chernoff bound implies that the sample size is \(O(\log n)\) with probability at least \(1-1/(2n^2)\).

Now assume that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N)\) never enters the if-block. Then the vertices \(\mathrm{DC}^j(u)\) for \(0\le j\le\lceil 2N_1^\beta\rceil\) are distinct consistent vertices of type \(r_T\). Consider the \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instances attached to them. Since these sub-instances are vertex-disjoint and all contained in \(I\), their total size is at most \(n^\star\). This means that at least \(N_1^\beta\) of them have a \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instance of size at most \(n^\star/N_1^\beta\) attached. The probability that none of these vertices is sampled is at most \((1-\delta)^{N_1^\beta} \le \exp(-4\log n) \le \frac{1}{2n^2}\) for all sufficiently large \(n\). A union bound over two events proves the lemma. ◻

Proof. Fix a vertex \(u\) and the first size parameter \(N_1\). If \(u=\perp\), if \(u\) is inconsistent, or if \(u\) is consistent with \(t(u)=\perp\), then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(u,N_1,2N_2)\) returns an output independent of \(N_2\). Thus we may take \(N_2^\star(u,N_1)=N_1\).

Suppose next that \(u\) lies in a \(\Pi_{\mathsf{HC}}^{T_L}\) sub-instance. Then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2)\) returns the output of \(\mathcal{A}_L(u,\lceil N_1^{1-\beta}\rceil,2N_2)\). By condition (i) for \(\mathcal{A}_L\), there is a threshold \(M^\star\) for the third parameter of \(\mathcal{A}_L\). Taking \(N_2^\star(u,N_1)\) to be the smallest integer \(N_2\ge N_1\) with \(2N_2\ge M^\star\) gives the desired statement. The argument for \(u\) in a \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instance is identical, using the threshold \(M^\star\) for \(\mathcal{A}_R(u,\lceil N_1^{1-\beta}\rceil,\star)\) and taking the smallest \(N_2\ge N_1\) such that \(\lceil 2N_2N_1^{-\beta}\rceil\ge M^\star\).

It remains to consider a consistent vertex \(u\) with \(t(u)=r_T\). For every integer \(p\ge 0\), the output of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p)\) depends only on \(u,N_1,p\) and the fixed randomness, and not on the value of \(N_2\). If there exists \(p\) such that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, p) \ne \perp\), take the minimum of them, denoted as \(p^\star\), and take \(N_2^\star(u, N_1)\) to be the smallest \(N_2 \ge N_1\) such that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u, N_1, N_2)\) calls \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1, p^\star)\); Otherwise the output label will be \((\mathsf{D}, 0)\) whatever the value of \(N_2\). Both cases satisfy condition (i). ◻

Proof. For each call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,k,N_1,N)\) in \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2)\), we first have \(N_1 \le N \le 2N_2\). Additionally, \(k \le \lceil 2N_1^\beta \rceil\) and \(\mathrm{DC}^j(u)\) is consistent for each \(0 \le j \le k\): whenever \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) is called from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\), all these vertices were visited before the first terminating event, and whenever \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) is called from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\), \(j^\star \in S_u\) already indicates that \(j^\star \le \lceil 2N_1^\beta \rceil\) and all indices between zero and \(j^\star\) passes the termination check in line [line:alg-poly-traverse-check-terminate] of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\).

For the first claim, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) uses \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) with size parameter \((N_1, N)\) to obtain the output bit of each \(\mathrm{LC}(\mathrm{DC}^j(u))\), while the output label of \(\mathrm{LC}(\mathrm{DC}^j(u))\) is generated by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{LC}(\mathrm{DC}^j(u)), N_1, 2N_2)\) inside \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(\mathrm{LC}(\mathrm{DC}^j(u)), N_1, N_2)\). If \(\mathrm{LC}(\mathrm{DC}^j(u))\) falls into an edge case handled directly by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\), its output is independent of the size parameter. Otherwise, condition (i) for \(\mathcal{A}_L\) implies that, if \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{LC}(\mathrm{DC}^j(u)), N_1, N)\) returns an output label other than \((\mathsf{D}, 0)\), this label must be the final output label for \(\mathrm{LC}(\mathrm{DC}^j(u))\). When \(\mathrm{LC}(\mathrm{DC}^j(u)) = \perp\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) outputs \((\mathsf{X},0)\). In sum, no matter when \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) returns a bit, every \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) call has returned an output label other than \((\mathsf{D},0)\), and the output bit is indeed \(b''(\mathrm{DC}^j(u))\) defined in ?? . If a call returns \((\mathsf{D},0)\), then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) fails and returns \(\perp\) instead of a bit. This concludes the first claim.

For the second claim, for each \(0 \le j \le k\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u, N_1, N)\) generates a call \(\mathcal{A}_L(\mathrm{LC}(\mathrm{DC}^j(u)), \lceil N_1^{1-\beta}\rceil, N)\) when \(\mathrm{LC}(\mathrm{DC}^j(u))\) does not fall into the edge cases. For each \(0 \le j \le k\), we define \(m_j\) to be the size of the \(\Pi_{\mathsf{HC}}^{T_L}\) sub-instance attached to \(\mathrm{DC}^j(u)\), and \(m_j = 0\) when it does not exist. These sub-instances are vertex-disjoint, so we have \(\sum_{j=0}^k m_j \le N\). This means that \(m_j \le N\) for each \(0 \le j \le k\), and additionally \(\lceil N_1^{1-\beta}\rceil\le N_1\le N\), so we can apply condition (iii) for \(\mathcal{A}_L\) to show that all of the \(\mathcal{A}_L\) calls return labels other than \((\mathsf{D}, 0)\).

We need to show further that the probe budget will not be used up by these \(\mathcal{A}_L\) calls. If \(T_L=\perp\), then each call uses \(O(1)\) probes, and the total cost is \(O(N_1^\beta) = O(NN_1^{\alpha-1})\) because \(N\ge N_1\) and \(\alpha = \beta\) when \(p = 0\). The case \(T_L = \bullet\) is impossible since then \(p = 1 \ge q\), contradicting the goodness of \(T\). In all remaining cases, the vertices queried are consistent vertices of type \(r_{T_L}\) in \(\Pi_{\mathsf{HC}}^{T_L}\) sub-instances, so we apply ?? in condition (iv), and the total number of probes is \[\begin{align} & \sum_{j=0}^k O\left(\max(\lceil N_1^{1-\beta}\rceil, m_j)\lceil N_1^{1-\beta}\rceil^{p-1} \log^{d_{T_L}} n\right) \\ = & O\left(\left(N_1 \cdot N_1^{(1-\beta)(p-1)}+N N_1^{(1-\beta)(p-1)}\right)\log^{d_T} n\right) \rceil=\Theta(N_1^{1-\beta}), k=O(N_1^\beta) and \sum_{j=0}^k m_j\le N} \\ = & O \left(N N_1^{(p-1)(1-\beta)} \log^{d_T} n\right)\\ = & O \left(N N_1^{\alpha - 1} \log^{d_T} n\right) } \end{align}\] This is within the probe budget when we set the probe budget constant in \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) to be sufficiently large. ◻

Proof. Let \(N=2^pN_1\). The sample set \(S_u\) is the same between \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p)\) and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p+1)\) according to 16, so it is enough to prove that every \(j\in S_{u,p}'\) belongs to \(S_{u,p+1}'\). Write \(x=\mathrm{RC}(\mathrm{DC}^j(u))\), and compare the calls \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x, N_1, N)\) and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x, N_1, 2N)\).

If \(x\) lies in edge cases handled directly by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\), then the output is independent of the size parameter. This covers the cases \(x=\perp\), \(x\) is inconsistent, and \(t(x)=\perp\). The case where \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) returns \(\perp\) is impossible here: if \(x\) is consistent, then \(x\) is the right child of a consistent type-\(r_T\) vertex and therefore has type \(\mathrm{RC}_T(r_T)\), or type \(\perp\) when \(\mathrm{RC}_T(r_T)=\perp\). Hence \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x,N_1,2N)\) is an output label other than \((\mathsf{D},0)\) whenever \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x,N_1,N)\) is one, and \(j \in S_{u,p+1}'\).

It remains to consider the case where \(x\) lies in a sub-instance. If \(x\) lies in a \(\Pi_{\mathsf{HC}}^{T_L}\) sub-instance, then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x,N_1,N)\) calls \(\mathcal{A}_L(x,\lceil N_1^{1-\beta}\rceil,N)\). Since this value is not \((\mathsf{D},0)\), condition (i) for \(\mathcal{A}_L\) implies that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(x,N_1,2N)\) would give the same output. The argument for a \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instance is identical. Thus \(j\in S_{u,p+1}'\), completing the proof. ◻

Proof. Let \(v = \mathrm{DC}(u)\). The backup label is returned only when \(S_{u,p_u^\star}'=\varnothing\) and the backup label produced by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N_u)\) is not \((\mathsf{D},0)\). According to [obs:poly-upper-bound-sample-set-monotone], we also know that \(S_{u,p}' = \varnothing\) for every \(0 \le p < p_u^\star\).

First suppose this label is \((\mathsf{Cyc},0)\). Then for some \(\ell \in [1, \lceil 2N_1^{\beta} \rceil]\), \(\mathrm{DC}^\ell(u)=u\), and all vertices on this directed cycle are consistent vertices of type \(r_T\). Additionally, every \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N)\) call will see this cycle and produce backup label \((\mathsf{Cyc}, 0)\) whatever the value of \(N\) is, so \(p_u^\star = 0\). We claim that \(p_v^\star\) is also zero and the output label for \(v\) will be \((\mathsf{Cyc}, 0)\), then the \(\Pi_{\mathsf{HC}}^T\) constraints on \(u\) are satisfied.

To see this, consider the call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(v, N_1, 0)\). It calls \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(v,N_1,N_1)\), which will see the cycle and prepare \((\mathsf{Cyc}, 0)\) for the backup label. Additionally, this call will visit exactly the same set of vertices as in \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N_1)\), and the sampling is consistent across calls of the same \(N_1\) value, this means that \(S_v\) will point to the same set of vertices as \(S_u\). Since \(S_{u,0}' = \varnothing\), \(S_{v,0}'\) will also be empty and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(v, N_1, 0)\) will output the backup label \((\mathsf{Cyc}, 0)\).

Now suppose the backup label is \((\mathsf{U},b_0)\). This means \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\) reaches a vertex \(\mathrm{DC}^j(u)\) that is either \(\perp\) or inconsistent, \(u, \mathrm{DC}(u), \mathrm{DC}^2(u), \dots, \mathrm{DC}^{j-1}(u)\) are all consistent vertices of type \(r_T\), and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,j-1,N_1,N_u)\) returns \(b_0\). If \(j = 1\), \(\mathrm{DC}(u)\) is \(\perp\) or colored \((\perp, 0)\), satisfying item 2 in the \(c_{\mathrm{out}}\) constraints for \(u\), and from 18, \(b_{\mathrm{out}}(u) = b_{\mathrm{in}}(u) \oplus b''(u)\), which is just ?? with \(b'(u) = 0\).

Next, we consider the case where \(j > 1\), then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(v, N_1, N_u)\) will see the same terminating event by traveling along a suffix of the DC path traveled by \(u\), and the corresponding \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call collects a subset of bits from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,j-1,N_1,N_u)\). This means that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(v, N_1, N_u)\) successfully generates a backup label \((\mathsf{U}, b_0')\). It is possible that the backup label can be produced with a smaller guess: Define \(p_v'\) as the smallest guess \(p\) such that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(v, N_1, 2^pN_1)\) produces a backup label other than \((\mathsf{D}, 0)\). From the argument above, we know \(p_v' \le p_u^\star\). In the remaining, we show that \(p_v^\star = p_v'\) and the output label for \(v\) makes \(u\) satisfy its \(\Pi_{\mathsf{HC}}^T\) constraints.

We have \(S_v \subseteq S_u\), so similar to the argument in the cycle case, \(S_{v,p}' = \varnothing\) for \(0 \le p \le p_u^\star\). This means that for each such \(p\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\) will check whether the backup label is not \((\mathsf{D}, 0)\). As \(p_v'\) is the smallest possible \(p\) value that generates a backup label other than \((\mathsf{D}, 0)\) and \(p_v' \le p_u^\star\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(v,N_1,p_v')\) will output the backup label while smaller \(p\) outputs \(\perp\). This proves \(p_v' = p_v^\star\). Since the backup label colors \(v\) with \(\mathsf{U}\), item 2 in the \(c_{\mathrm{out}}\) constraint is satisfied on \(u\). For the \(b_{\mathrm{out}}\) constraint, according to 18, we have \[\begin{gather} b_{\mathrm{out}}(u) = \bigoplus_{r=0}^{j-1}\left(b_{\mathrm{in}}(\mathrm{DC}^r(u))\oplus b''(\mathrm{DC}^r(u))\right), \\ b_{\mathrm{out}}(v) = \bigoplus_{r=1}^{j-1}\left(b_{\mathrm{in}}(\mathrm{DC}^r(u))\oplus b''(\mathrm{DC}^r(u))\right). \end{gather}\] As a result, we have \(b_{\mathrm{out}}(u) = b_{\mathrm{out}}(v) \oplus b_{\mathrm{in}}(u) \oplus b''(u)\), which is ?? .

In both cases, it remains to consider item 5 in the \(c_{\mathrm{out}}\) constraints that \(\mathrm{LC}(u)\) should not be labeled \((\mathsf{D}, 0)\). This comes from the fact that the \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call, which would fail when one of the left children is labeled \((\mathsf{D}, 0)\), outputs a bit rather than a failure. ◻

Proof. Since \(0\in S_{u,p_u^\star}'\), the minimum index \(j^\star\) chosen is zero. Thus, the branch for \(j^\star=0\) sets \(c^\star=\mathsf{X}\). As \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p_u^\star)\) succeeds, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,0,N_1,N_u)\) returns a bit, and the algorithm returns a label of color \(\mathsf{X}\).

The color \(\mathsf{X}\) is allowed at \(u\) because \(u\) has type \(r_T\) and \(r_T\) is not a leaf. As \(0\in S_{u,p_u^\star}'\), the call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{RC}(u),N_1,2^{p_u^\star}N_1)\) returns a label other than \((\mathsf{D},0)\). Since \(2^{p_u^\star}N_1\le 2N_2\), by condition (i) of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\), this will be the output label for \(\mathrm{RC}(u)\). This proves item 3(b) in the constraint on \(c_{\mathrm{out}}\). Similarly, the successful \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call implies, by 18, that the output label of \(\mathrm{LC}(u)\) is not \((\mathsf{D},0)\), proving item 5. In sum, \(c_{\mathrm{out}}\) constraints on \(u\) are satisfied.

Let \(b^\star\) be the output bit of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{RC}(u),N_1,2^{p_u^\star}N_1)\), then \(b^\star\) equals \(b_{\mathrm{out}}(\mathrm{RC}(u))\) when \(\mathrm{RC}(u)\) exists, and equals zero if \(\mathrm{RC}(u)=\perp\). This is exactly the definition of \(b'(u)\) in ?? . By 18, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,0,N_1,2^{p_u^\star}N_1)\) returns \(b_{\mathrm{in}}(u)\oplus b''(u)\). Therefore \(b_{\mathrm{out}}(u) = b_{\mathrm{in}}(u)\oplus b''(u)\oplus b^\star\), which is exactly ?? for a vertex of color \(\mathsf{X}\). ◻

Proof. Define \(y=\mathrm{DC}^j(u)\). When \(c_{\mathrm{out}}(y) = \mathsf{Cyc}\), the cycle containing \(y\) must contain \(u\) as otherwise the consistency will be violated. Then from the argument in 19, \(c_{\mathrm{out}}(u)\) should also be \(\mathsf{Cyc}\), a contradiction.

Another possibility is that \(c_{\mathrm{out}}(y) = \mathsf{X}\). This happens only when \(0\in S_{y,p_y^\star}'\), which by consistent sampling would imply \(j \in S_{u,p_y^\star}'\). According to [obs:poly-upper-bound-sample-set-monotone], to make sure \(j^\star > j\) is the minimum among \(S_{u,p_u^\star}'\), \(p_y^\star > p_u^\star\) must hold.

However, we will prove next that \(p_y^\star \le p_u^\star\), leading to a contradiction. Notice that \(j^\star\) is the minimum value in \(S_{u,p_u^\star}'\) implies that \(j^\star-j\) is the minimum value in \(S_{y,p_u^\star}'\). As a result, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(y, N_1, p_u^\star)\) will agree on the same vertex \(w\) as \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, p_u^\star)\), the check \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w, N_1, N_u/2) \ge 0\) has the same result, and the corresponding \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call in \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(y,N_1,p_u^\star)\) collects a subset of bits compared to the successful \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call in \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, p_u^\star)\). This means that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(y,N_1,p_u^\star)\) returns a label rather than a failure and \(p_y^\star \le p_u^\star\).

Since we have proved \(p_y^\star \le p_u^\star\), \(c_{\mathrm{out}}(y)\) cannot be \(\mathsf{D}\) either. So the only possible color for \(y\) is \(\mathsf{U}\), concluding the statement. ◻

Proof. We prove the statement by induction on \(p_u^\star\). This means that, to show the statement for a vertex \(u\), we assume that the induction hypothesis holds for every consistent vertex \(u'\) of type \(r_T\) with \(p_{u'}^\star < p_u^\star\). Let \(j^\star=\min S_{u,p_u^\star}'\) and \(w=\mathrm{DC}^{j^\star}(u)\), then \(j^\star \ge 1\). \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\) then checks whether \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w,N_1,N_u/2)\ne(\mathsf{D},0)\), and enters one of the two branches starting at lines [line:alg-poly-upper-bound-prev-success-block] and [line:alg-poly-upper-bound-prev-fail-block]. As \(N_u = 2^{p_u^\star} N_1\), this is equivalent to checking whether \(p_w^\star < p_u^\star\).

Consider first the branch where \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w,N_1,N_u/2)\ne(\mathsf{D},0)\). Then, according to condition (i) for \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\), the label returned by this call is the output label of \(w\), and we know \(p_w^\star < p_u^\star\). The case where \(c_{\mathrm{out}}(w) = \mathsf{Cyc}\) cannot exist: as otherwise the \(\mathrm{DC}\) cycle from \(w\) should pass \(u\), and \(c_{\mathrm{out}}(u)\) should also be \(\mathsf{Cyc}\) according to 19, a contradiction. \(p_w^\star < p_u^\star\) implies that \(c_{\mathrm{out}}(w) \ne \mathsf{D}\), thus \(w\) is colored \(\mathsf{X}\) or \(\mathsf{U}\).

If \(w\) is colored \(\mathsf{X}\), we set \(i^\star_u=j^\star\). 21 shows that for all \(0 \le j < j^\star\), \(c_{\mathrm{out}}(\mathrm{DC}^j(u)) = \mathsf{U}\), so \(j^\star\) is the correct value for \(i^\star_u\). If \(w\) is colored \(\mathsf{U}\), \(w\) receives this label from two possible places: one is from the backup label produced by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\), in which, according to the proof in 19, there exists a value \(i^\star_w\) such that \(\mathrm{DC}^{i^\star_w}(w)\) is inconsistent or \(\perp\) and all vertices between \(w\) and \(\mathrm{DC}^{i^\star_w - 1}(w)\) are colored \(\mathsf{U}\). As a result, \(i^\star_u\) exists and equals \(j^\star+i^\star_w\). The final case is that \(S_{w,p_w^\star}' \ne \varnothing\) and \(0 \not\in S_{w,p_w^\star}'\). In this case, since \(p_w^\star < p_u^\star\), we can apply the induction hypothesis to get \(i^\star_w\), and assign \(i^\star_u=i^\star_w + j^\star\). The arguments above in sum prove item 1).

The item 2 in the \(c_{\mathrm{out}}\) constraint on \(u\) follows because \(\mathrm{DC}(u)\) is either \(\perp\), inconsistent, or colored \(\mathsf{X}\) when \(i^\star_u=1\), and colored \(\mathsf{U}\) when \(i^\star_u>1\); also, the successful \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call implies that \(\mathrm{LC}(u)\) is not colored \(\mathsf{D}\) if it exists, so item 5 in the \(c_{\mathrm{out}}\) constraint is also satisfied. This proves item 2).

For items 3), notice that the \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call in this branch uses parameter \((u,j^\star-1,N_1,N_u)\), and it returns a bit \(B\) because \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p_u^\star)\) succeeds. By 18, the algorithm returns \(b_{\mathrm{out}}(u)=b_{\mathrm{out}}(w)\oplus B\) with \[B=\bigoplus_{i=0}^{j^\star-1} \left(b_{\mathrm{in}}(\mathrm{DC}^i(u))\oplus b''(\mathrm{DC}^i(u))\right).\]

If \(w\) is colored \(\mathsf{X}\), then substituting ?? for \(w\) proved in 20 gives ?? . If \(w\) is colored \(\mathsf{U}\) and receives the backup label from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(w,N_1,p_w^\star)\), the proof of 19 implies that \(b_{\mathrm{out}}(w) = \bigoplus_{i=0}^{i^\star_w - 1}(b_{\mathrm{in}}(\mathrm{DC}^i(w)) \oplus b''(\mathrm{DC}^i(w)))\), and this gives ?? . Finally, the case where \(w\) receives a label since \(S_{w,p_w^\star}' \ne \varnothing\) and \(0 \not\in S_{w,p_w^\star}'\) follows from the induction hypothesis.

It remains to consider the branch where \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w,N_1,N_u/2)=(\mathsf{D},0).\) In this case, we know \(p_w^\star \ge p_u^\star\). Since \(j^\star \in S_{u,p_u^\star}'\), the consistent sampling implies that \(0\in S_{w,p_u^\star}'\). Moreover, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(w,0,N_1,N_u)\) will succeed since it collects a subset of bits compared to the successful call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,j^\star,N_1,N_u)\). As a result, from 20, we know that \(p_w^\star = p_u^\star\), the output color for \(w\) will be \(\mathsf{X}\), and its local constraints are satisfied.

We set \(i^\star_u=j^\star\), then 21 immediately implies item 1). Also, the successful \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,j^\star,N_1,N_u)\) call implies that \(\mathrm{LC}(u)\) is not colored \(\mathsf{D}\) if it exists, so the \(c_{\mathrm{out}}\) constraint on \(u\) is satisfied, implying item 2).

For item 3), notice that the successful \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi(u,j^\star,N_1,N_u)\) call returns a bit \(B\) with \[B=\bigoplus_{j=0}^{j^\star} \left(b_{\mathrm{in}}(\mathrm{DC}^j(u))\oplus b''(\mathrm{DC}^j(u))\right)\] according to 18. At the same time, condition (i) for \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\) implies that the bit \(b^\star\) obtained from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{RC}(w), N_1, N)\) is exactly \(b'(w)\). Since \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p_u^\star)\) returns \(b^\star\oplus B\), this gives ?? . ◻

Proof. Fix \(N_2\ge N_1\) and consider the output labeling generated by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2)\). Inconsistent vertices, vertices of type \(\perp\), and vertices in \(\Pi_{\mathsf{HC}}^{T_L}\) or \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instances satisfy all relevant constraints by the definition of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) and the induction hypothesis. Hence it remains to consider a consistent vertex \(u\) with \(t(u)=r_T\).

If \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2)\) returns \((\mathsf{D},0)\), then the only possible violation is item 4 in the constraint on \(c_{\mathrm{out}}\), which is explicitly allowed in condition (ii). Otherwise \(p_u^\star\) is defined. If \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p_u^\star)\) returns the backup label from \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\), the constraints on \(u\) are satisfied by 19. Otherwise \(S_{u,p_u^\star} \ne \varnothing\). If \(0\in S_{u,p_u^\star}'\), constraints on \(u\) are satisfied by 20. The remaining case is that \(S_{u,p_u^\star}'\ne\varnothing\) and \(0\notin S_{u,p_u^\star}'\), which is handled by 22. These lemmas cover every possible cases, so condition (ii) follows. ◻

Proof. Let \(N_2\ge \max(N_1,n^\star)\), and let \(u\) be a consistent vertex with \(t(u)=r_T\). Set \(p=\left\lceil \log_2(N_2/N_1)\right\rceil\) and \(N=2^pN_1\), then \(N_2\le N\le 2N_2\), and in particular \(N\ge n^\star\). Consider the call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,p)\), we will show that this call must return a label rather than a failure, so the output label for \(u\) is not \((\mathsf{D}, 0)\).

First of all, for every \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call during \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, p)\), all \(\Pi_{\mathsf{HC}}^{T_L}\) sub-instances are vertex-disjoint, so their total size is at most \(n^\star \le N\). According to 18, every \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call will succeed.

Now consider every possibility that \(u\) gets a label. If \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N)\) reaches a terminating event (i.e. reaching \(\perp\), an inconsistent vertex, or returning to itself) and produces a backup label, the corresponding \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) call always succeed, so a backup label other than \((\mathsf{D}, 0)\) is produced. This means that, when \(S_{u,p}' = \varnothing\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, p)\) still output a label other than \((\mathsf{D}, 0)\). When \(S_{u,p}' \ne \varnothing\), \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\) always outputs a label other than \((\mathsf{D}, 0)\) no matter the result of \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w, N_1, N/2)\) is.

For the other case that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi(u,N_1,N)\) does not produce a backup label, according to 16, there is an index \(j\in S_u\) whose attached \(\Pi_{\mathsf{HC}}^{T_R}\) sub-instance has size at most \(n^\star/N_1^\beta\). \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{RC}(\mathrm{DC}^j(u)),N_1,N)\) will invoke \(\mathcal{A}_R(\mathrm{RC}(\mathrm{DC}^j(u)), \lceil N_1^{1-\beta}\rceil, \lceil NN_1^{-\beta}\rceil)\). As \(\lceil N_1^{1-\beta}\rceil\le \lceil NN_1^{-\beta}\rceil\) and \(n^\star / N_1^\beta \le \lceil NN_1^{-\beta} \rceil\), condition (iii) for \(\mathcal{A}_R\) implies that this \(\mathcal{A}_R\) call returns a label other than \((\mathsf{D}, 0)\). Hence \(S_{u,p}'\) is nonempty, and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\) outputs a label other than \((\mathsf{D}, 0)\) following the same argument as above. ◻

Proof. Apart from the induction hypothesis for \(\mathcal{A}_L\) and \(\mathcal{A}_R\), we apply an induction on \(d\) to prove the following three claims simultaneously for the current instance of size \(n^\star\):

• For every \(0\le r\le d\), \[\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,r) \text{ uses } O(2^rN_1^\alpha\log^{d_T}n) \text{ probes.}\]

• For every \(N_1\le N_2\le N_12^d\) and every vertex \(u\), \[\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2) \text{ uses } O(N_2N_1^{\alpha-1}\log^{d_T}n) \text{ probes.}\]

• For every \(N_1\le N_2\le N_12^d\) and every consistent vertex \(u\) with \(t(u)=r_T\), \[\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(u,N_1,N_2) \text{ uses } O(\max(N_1,n^\star)N_1^{\alpha-1}\log^{d_T}n) \text{ probes.}\]

The claims B\(_{\mathrm{all}}(d)\) and B\(_{\mathrm{root}}(d)\) for all \(d\ge 0\) are exactly the two bounds in condition (iv). The base case for \(d=-1\) is trivial. We show B\(_{\mathrm{all}}(d-1)\Rightarrow\) A(\(d\)), and then A(\(d)\Rightarrow\) B\(_{\mathrm{all}}(d)\) and B\(_{\mathrm{root}}(d)\), concluding the induction.

We first show B\(_{\mathrm{all}}(d-1)\Rightarrow\) A(\(d\)). Fix \(0\le r\le d\) and set \(N=2^rN_1\). Consider the subroutines that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,r)\) calls. It makes only constantly many \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Collect}}}^T\nolimits\else\textrm{\mathrm{\small Collect}}^T\fi\) calls, each with budget \[O(NN_1^{\alpha-1}\log^{d_T}n) = O(2^rN_1^\alpha\log^{d_T}n).\] The \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Traverse}}}^T\nolimits\else\textrm{\mathrm{\small Traverse}}^T\fi\) call uses \(O(N_1^\beta)\le O(N_1^\alpha)\le O(N_1^\alpha)\) probes. For each sampled index \(j\in S_u\), the call to \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(\mathrm{RC}(\mathrm{DC}^j(u)),N_1,N)\) is either handled directly in \(O(1)\) probes, or invokes \(\mathcal{A}_R(\mathrm{RC}(\mathrm{DC}^j(u)),\lceil N_1^{1-\beta}\rceil,\lceil NN_1^{-\beta}\rceil)\). By induction hypothesis, applying ?? for \(\mathcal{A}_R\), we know that each of these calls costs \[\begin{align} &O\left(NN_1^{-\beta}\cdot N_1^{(1-\beta)(q-1)}\log^{d_T - 1}n\right)\le d_T - 1}\\ ={}&O\left(NN_1^{\alpha-1}\log^{d_T-1}n\right). {1+q-p} + \frac{q-1}{1+q-p} = \frac{p-1}{1+q-p} = \alpha-1} \end{align}\] Since \(|S_u|=O(\log n)\) by 16, all calls together cost \(O(NN_1^{\alpha-1}\log^{d_T}n)\). Finally, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi\) may call \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi(w,N_1,N/2)\). If \(r=0\), this call returns immediately because \(N/2<N_1\). Otherwise, B\(_{\mathrm{all}}(d-1)\) applies and gives cost \[O((N/2)N_1^{\alpha-1}\log^{d_T}n) = O(NN_1^{\alpha-1}\log^{d_T}n).\] In sum, \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u, N_1, r)\) has a cost of \(O(2^rN_1^\alpha \log^{d_T} n)\). This proves A(\(d\)).

We now prove B\(_{\mathrm{all}}(d)\) from A\((d)\). The initial \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(u,N_1,2N_2)\) may call one of \(\mathcal{A}_L\) and \(\mathcal{A}_R\). By ?? applied to both \(\mathcal{A}_L\) and \(\mathcal{A}_R\), the call \(\mathcal{A}_L(u,\lceil N_1^{1-\beta}\rceil,2N_2)\) costs \[O(N_2N_1^{(1-\beta)(p-1)}\log^{d_{T_L}}n) = O(N_2N_1^{\alpha-1}\log^{d_T}n), }\] and the call \(\mathcal{A}_R(u, \lceil N_1^{1-\beta}\rceil,\lceil 2N_2N_1^{-\beta}\rceil)\) costs \[O(N_2N_1^{-\beta}N_1^{(1-\beta)(q-1)}\log^{d_{T_R}}n) = O(N_2N_1^{\alpha-1}\log^{d_T}n).\] If \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi\) returns a label, this proves B\(_{\mathrm{all}}(d)\). Otherwise, \(u\) is a consistent vertex of type \(r_T\), and \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\) runs \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,r)\) over a geometric sequence of size guesses all the way up to \(2N_2\). By A(\(d\)), the total cost of all these calls is \(O(N_2N_1^{\alpha-1}\log^{d_T}n)\). This proves B\(_{\mathrm{all}}(d)\).

It remains to prove B\(_{\mathrm{root}}(d)\) from A\((d)\). Let \(u\) be a consistent vertex with \(t(u)=r_T\). Then \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Prepare}}}^T\nolimits\else\textrm{\mathrm{\small Prepare}}^T\fi(u,N_1,2N_2)\) returns \(\perp\) with \(O(1)\) probes. When \(N_2<n^\star\), B\(_{\mathrm{all}}(d)\) already implies B\(_{\mathrm{root}}(d)\), so we consider the other case where \(N_2\ge n^\star\). The proof of 24 shows that \(\ifmmode\mathop{\text{\normalfont\mathrm{\small Try}}}^T\nolimits\else\textrm{\mathrm{\small Try}}^T\fi(u,N_1,r)\) succeeds as soon as \(2^rN_1 \ge n^\star\). Therefore the largest size guess used by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\) is \(O(\max(N_1,n^\star))\), and the probe complexity forms a geometric sequence according to A(\(d\)). As a result, they sum up to \[O(\max(N_1,n^\star)N_1^{\alpha-1}\log^{d_T}n),\] which is the desired bound. This proves B\(_{\mathrm{root}}(d)\) and completes the proof of condition (iv). ◻

Proof of 4. The proof is by induction on the size of \(T\). The base cases are 14 15. For the induction part, assume that for some tree \(T\) there is a strong algorithm for \(\Pi_{\mathsf{HC}}^{T_L}\) and \(\Pi_{\mathsf{HC}}^{T_R}\), then the algorithm is given by \(\ifmmode\mathop{\text{\normalfont\mathrm{\small SolveHC}}}^T\nolimits\else\textrm{\mathrm{\small SolveHC}}^T\fi\). For the conditions, when all the events described in the start of the analysis section happens, which is of probability at least \(1-n^\star/n^2\), all four conditions in 13 are satisfied shown in 17 23 24 25. ◻

Proof. We prove the lemma by induction on the size of \(T\).

First, consider the base case \(T=\bullet\). \(\mathcal{S}_{\bullet,n}\) contains all instances with the following property: The underlying graph is a directed \(\mathrm{DC}\) path \(u_1,u_2,\ldots,u_n\), where \(u_1=x\); in the \(T\)-labeling, all vertices have type \(r_T\), all \(\mathrm{LC}\) and \(\mathrm{RC}\) ports are \(\perp\). There is no constraint on \(b_{\mathrm{in}}\) inputs on each vertex, so \(\mathcal{S}_{\bullet,n}\) contains \(2^n\) instances, one different \(b_{\mathrm{in}}\) assignment per instance.

Condition (i) is satisfied by definition. Since \(r_T\) is a leaf and a root, \(\mathsf{X}\) and \(\mathsf{D}\) are prohibited. Moreover, no vertex can output \(\mathsf{Cyc}\). Thus, every legal solution colors each vertex with \(\mathsf{U}\), and ?? gives \(b_I = b_{\mathrm{out}}(x)=\bigoplus_{i=1}^n b_{\mathrm{in}}(u_i)\). This proves condition (ii). Finally, for any \(V_0\) of size \(o(n)\), choose \(w\notin V_0\) and map an instance to the instance obtained by flipping only \(b_{\mathrm{in}}(w)\). This map is clearly a bijection between \(\mathcal{S}_{\bullet,n}^0\) and \(\mathcal{S}_{\bullet,n}^1\), and it preserves all input bits on \(V_0\). Hence condition (iii) holds.

Now assume that \(T \ne \bullet\), and write \[p=\operatorname{val}(T_L),\qquad q=\operatorname{val}(T_R),\qquad \alpha=\operatorname{val}(T),\qquad \beta=\frac{q-p}{1+q-p}.\] Since \(T\) is good, we have \(p<q\). Let \(\ell=\Theta(n^\beta)\) and \(m=\Theta(n^{1-\beta})\), and we define \(\mathcal{S}_{T,n}\) as all instances that can be generated by the following procedure:

• Create a directed \(\mathrm{DC}\) path \(x = u_1,u_2,\ldots,u_\ell\) of length \(\ell\), all of which have type \(r_T\).

• Generate \((A_1,\ldots,A_\ell) \in \{0,1\}^\ell\) and define \(S_i=A_{i+1}\oplus A_{i+2}\oplus\cdots\oplus A_\ell\) for \(0 \le i < \ell\) and \(S_\ell = 0\).

• If \(T_L=\perp\), then for every vertex \(u_i (1 \le i \le \ell)\), set \(\mathrm{LC}(u_i)=\perp\) and \(b_{\mathrm{in}}(u_i)=A_i\). Otherwise, we set \(b_{\mathrm{in}}(u_i)=0\) and attach to \(\mathrm{LC}(u_i)\) an arbitrary instance drawn from \(\mathcal{S}_{T_L,m}^{A_i}\).

• For every \(i \in [1,\ell]\), attach to \(\mathrm{RC}(u_i)\) an arbitrary instance drawn from \(\mathcal{S}_{T_R,m}^{S_i}\).

For “attaching an instance to a port”, we mean creating a copy of the instance, making the port point to the root of the copy, and setting the parent port of that copied root back to the vertex \(u_i\). The constants hidden in \(\Theta(\cdot)\) are chosen so that the final instance has at most \(n\) and \(\Theta(n)\) vertices. This completes the definition of \(\mathcal{S}_{T,n}\).

According to the induction hypothesis, the structure and \(T\)-labeling of the attached instance is fixed, while the structure and \(T\)-labeling of the top-level \(\mathrm{DC}\) path is also fixed. Hence all instances in \(\mathcal{S}_{T,n}\) have the same underlying graph and \(T\)-labeling, in which it is easy to prove that the graph is a tree, every vertex is consistent, and the only type-\(r_T\) vertex with parent \(\perp\) is \(x=u_1\). Thus condition (i) holds.

Now we consider condition (ii). Define the contribution of a vertex \(u_i\), denoted as \(c(u_i)\), as \(b''(u_i) \oplus b_{\mathrm{in}}(u_i)\), where \(b''\) is defined in ?? . According to the construction, \(c(u_i) = A_i\) for each \(1 \le i \le \ell\). Now, for any legal output, define \(k = \min\{i \mid c_{\mathrm{out}}(u_i) = \mathsf{X}\}\), and \(k = \infty\) when there is no such \(i\). Notice that \(\mathsf{Cyc}\) is prohibited since there is no cycle in the instance. When \(k \ne \infty\), expanding ?? gives \[b_{\mathrm{out}}(x)=c(u_1) \oplus \dots \oplus c(u_k) \oplus S_k = A_1\oplus\cdots\oplus A_k\oplus S_k= \oplus_{i=1}^\ell A_i.\] If \(k = \infty\), then we have \[b_{\mathrm{out}}(x)=c(u_1) \oplus \dots \oplus c(u_\ell) = A_1\oplus\cdots\oplus A_\ell=\oplus_{i=1}^\ell A_i.\] In all, condition (ii) is satisfied by \(b_I = \oplus_{i=1}^\ell A_i\).

It remains to prove condition (iii). Define \(L_i\) and \(R_i\) as the \(\Pi_{\mathsf{HC}}^{T_L}\) and \(\Pi_{\mathsf{HC}}^{T_R}\) instance attached to \(u_i\), with \(L_i=\varnothing\) when \(T_L=\perp\). For a fixed set of vertices \(V_0\) of size \(o(n^{\operatorname{val}(T)})\), let \(V_i^L = V_0 \cap L_i\) and \(V_i^R = V_0 \cap R_i\). We have \[|V_i^R| = o(n^\alpha) = o(n^{q(1-\beta)}) = o(m^q),\] so according to the induction hypothesis, for each \(i \in [1,\ell]\) there exists a bijection \(f^R_i\) between \(\mathcal{S}_{T_R, m}^0\) and \(\mathcal{S}_{T_R, m}^1\) satisfying condition (iii) for \(V_i^R\). Additionally, when \(T_L \ne \perp\), we have \[\min_i |V_i^L| \le \frac{1}{\ell} \sum_{i=1}^\ell |V_i^L| \le \frac{o(n^\alpha)}{\ell} = o(n^{\alpha - \beta}) = o(n^{p(1-\beta)}) = o(m^p).\] Take \(i^\star = \arg \min_i |V_i^L|\), then according to the induction hypothesis, there exists a bijection \(f^L_{i^\star}\) between \(\mathcal{S}_{T_L, m}^0\) and \(\mathcal{S}_{T_L, m}^1\) satisfying condition (iii) for \(V_{i^\star}^L\). For the case where \(T_L = \perp\), \(\alpha = q/(1+q) = \beta\), so \(|V_0| = o(n^\beta)\) and there exists some \(i^\star\) where \(u_{i^\star} \not\in V_0\). We let \(f_{i^\star}^L\) denote the operation that flips \(b_{\mathrm{in}}(u_{i^\star})\).

Now we construct the bijection \(f_{V_0}\) between \(\mathcal{S}_{T,n}^0\) and \(\mathcal{S}_{T,n}^1\). For each instance \(I\) in \(\mathcal{S}_{T,n}\) with bits \(A_1, A_2, \dots, A_\ell\), we flip \(A_{i^\star}\) by replacing the \(\Pi_{\mathsf{HC}}^{T_L}\) instance attached to \(u_{i^\star}\) with its image in \(f_{i^\star}^L\) if \(T_L\ne\perp\), or by flipping \(b_{\mathrm{in}}(u_{i^\star})\) if \(T_L=\perp\). For every \(1 \le i < i^\star\), the value \(S_i\) also flips, so we replace the \(\Pi_{\mathsf{HC}}^{T_R}\) instance attached to \(u_i\) with its image under \(f_i^R\). All other inputs are unchanged. This completes the construction.

Since \(f_{i^\star}^L\) and all \(f_i^R\) are bijections, and the same components are changed when we apply the map again, \(f_{V_0}\) is an bijection. It remains to check that \(f_{V_0}\) flips \(b_I\). According to the induction hypothesis, the map changes exactly \(A_{i^\star}\) and \(S_1, S_2, \dots,S_{i^\star-1}\). By following the same analysis for condition (ii), we know that all solutions for \(f_{V_0}(I)\) must have \(b_{\mathrm{out}}(x) = b_I \oplus 1\), so \(f_{V_0}\) is indeed a bijection between \(\mathcal{S}_{T,n}^0\) and \(\mathcal{S}_{T,n}^1\).

Finally, we show that \(I\) and \(f_{V_0}(I)\) have the same input labels on \(V_0\). For replaced \(\Pi_{\mathsf{HC}}^{T_L}\) and \(\Pi_{\mathsf{HC}}^{T_R}\) copies, this follows from the induction hypothesis applied to \(V_{i^\star}^L\) and to the sets \(V_i^R\). All other attached instances are identical. Vertices in the top \(\mathrm{DC}\) chain keep the same input when \(T_L \ne \perp\), and when \(T_L = \perp\), the only input bit that changes is at \(u_{i^\star}\notin V_0\). This concludes condition (iii). ◻

Proof of 12. Suppose for contradiction that there is a randomized LCA that solves \(\Pi_{\mathsf{HC}}^T\) with \(o(n^{\operatorname{val}(T)})\) probes and succeeds in every \(\Pi_{\mathsf{HC}}^T\) instance of size at most \(n\) with probability larger than \(1/2\). Pick any distribution \(\mathcal{D}\) over instances of size at most \(n\). According to Yao’s minimax principle, there is a deterministic LCA \(\mathcal{A}\) with the same probe bound that succeeds with probability larger than \(1/2\) over \(\mathcal{D}\).

Now set \(\mathcal{D}\) to be a uniform distribution over \(\mathcal{S}_{T,n}\). Since all instances in the support have the same graph and \(T\)-labeling, the transcript of \(\mathcal{A}(x)\) is determined by the set of probed vertices and their \(b_{\mathrm{in}}\) values. Fix any possible transcript \(\tau\), and let \(V(\tau)\) be the set of vertices probed in this transcript. We have \(|V(\tau)|=o(n^{\operatorname{val}(T)})\). Applying condition (iii) of 26 to \(V(\tau)\) gives a bijection between \(\mathcal{S}_{T,n}^0\) and \(\mathcal{S}_{T,n}^1\) that preserves all input bits seen in \(\tau\). Since all instances have the same probability of being chosen, and by condition (ii), a correct output must have root bit \(b_I\), we have \(\Pr[b_I=0 \mid \tau]=\Pr[b_I=1 \mid \tau]=1/2\), and the success probability of \(\mathcal{A}\) over \(\mathcal{D}\) is at most \(1/2\), a contradiction. ◻