The Query Complexity of Searching Trees with Permanently Noisy Advice Article Swipe
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1145/3707207
· OA: W4405075937
We consider a search problem on trees aiming to find a treasure that an adversary places at one of the nodes. The algorithm can query nodes and extract directional information from them. That is, each node holds a pointer, termed advice , to one of its neighbors. Ideally, this advice points to the neighbor that is closer to the treasure, however, with probability \(q\) this advice points to a uniformly random neighbor. Crucially, the advice is permanent , hence querying the same node again yields the same answer. Let \(\Delta\) denote the maximal degree. Roughly speaking, we show that the expected number of queries incurs a phase transition when \(q\) is about \(1/\sqrt{\Delta}\) . In a recent paper, at TALG’21, we showed that if \(q\) is above the threshold then the expected number of queries is polynomial in \(n\) . Here, we prove that below the threshold, the expected number of queries is \(\mathcal{O}(\sqrt{\Delta}\log\Delta\cdot\log^{2}n)\) , which is tight up to an \(\mathcal{O}(\log n)\) factor when \(\Delta\) is small. We further show that this factor can be reduced to \(\mathcal{O}(\log\log n)\) in the case of regular trees and assuming that \(q<c/\sqrt{\Delta}\) for sufficiently small \(c>0\) . In addition, we study the case that the treasure must be found with some given probability. We show that for every fixed \(\varepsilon,\delta>0\) , if \(q<1/\Delta^{\varepsilon}\) then there exists a search strategy that with probability \(1-\delta\) finds the treasure using \((\delta^{-1}\log n)^{O(\frac{1}{\varepsilon})}\) queries, whereas \((\delta^{-1}\log n)^{\Omega(\frac{1}{\varepsilon})}\) queries are necessary.
