Navigating in Trees with Permanently Noisy Advice
Lucas Boczkowski, Uriel Feige, Amos Korman, Yoav Rodeh · ACM Transactions on Algorithms · 2021
We consider a search problem on trees in which an agent starts at the root of a tree and aims to locate an adversarially placed treasure, by moving along the edges, while relying on local, partial information. Specifically, each node in the tree holds a pointer to one of its neighbors, termedadvice. A node is faulty with probabilityq. The advice at a non-faulty node points to the neighbor that is closer to the treasure, and the advice at a faulty node points to a uniformly random neighbor. Crucially, the advice ispermanent, in the sense that querying the same node again would yield the same answer. Let Δ denote the maximum degree. For the expected number of moves (edge traversals) until finding the treasure, we show that a phase transition occurs when thenoise parameterqis roughly 1 √Δ. Below the threshold, there exists an algorithm with expected number of movesO(D√Δ), whereDis the depth of the treasure, whereas above the threshold, every search algorithm has an expected number of moves, which is both exponential inDand polynomial in the number of nodes n. In contrast, if we require to find the treasure with probability at least 1 − δ, then for every fixed ɛ > 0, ifq< 1/Δɛ, then there exists a search strategy that with probability 1 − δ finds the treasure using (Δ−1D)O(1/ε)moves. Moreover, we show that (Δ−1D)Ω(1/ε)moves are necessary.