The Query Complexity of Searching Trees with Permanently Noisy Advice

作     者：Boczkowski, Lucas Feige, Uriel Korman, Amos Rodeh, Yoav 

作者机构：IRIF CNRS Paris France Univ Paris Paris France Weizmann Inst Sci Rehovot Israel Univ Haifa Haifa Israel CNRS FILOFOCS Tel Aviv Israel ORT Braude Coll Karmiel Israel 

出 版 物：《ACM TRANSACTIONS ON ALGORITHMS》 (ACM Trans. Algorithms)

年 卷 期：2025年第21卷第2期

页      面：1-30页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

基　　金：Israel Science Foundation 

主　　题：Search algorithms Fault-tolerance Noisy advice Randomized algorithms Trees 

摘      要：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/root 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 O(root Delta log Delta center dot log(2)n), which is tight up to an O(logn) factor when Delta is small. We further show that this factor can be reduced to O(log log n) in the case of regular trees and assuming that q 0. In addition, we study the case that the treasure must be found with some given probability. We show that for every fixed epsilon, delta 0, if q 1/Delta(epsilon) then there exists a search strategy that with probability 1-delta finds the treasure using (delta(-1) logn)O ((1/epsilon)) queries, whereas (delta(-1) logn)(Omega(1/epsilon)) queries are necessary.