版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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[理学-基础数学]
主 题: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.