Navigating in Trees with Permanently Noisy Advice
Résumé
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, termed advice. A node is faulty with probability $q$. 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 is permanent, in the sense that querying the same node again would yield the same answer.
Let $\Delta$ denote the maximum degree. For the expected number of moves (edge traversals), we show that a phase transition occurs when the {\em noise parameter} $q$ is roughly $1/\sqrt{\Delta}$. Below the threshold, there exists an algorithm with expected number of moves $\bigO(D\sqrt{\Delta})$, where $D$ is the depth of the treasure, whereas above the threshold, every search algorithm has expected number of moves which is both exponential in $D$ and polynomial in the number of nodes~$n$.
In contrast, if we require to find the treasure with probability at least $1-\delta$, then
for every fixed $\epsilon > 0$, if $q<1/\Delta^{\epsilon}$ then there exists a search strategy that with probability $1-\delta$ finds the treasure using $(\delta^{-1}D)^{O(\frac 1 \epsilon)}$ moves. Moreover, we show that $(\delta^{-1}D)^{\Omega(\frac 1 \epsilon)}$ moves are necessary.
Origine : Fichiers produits par l'(les) auteur(s)