2016/06/10 by Ehsan Emamjomeh-Zadeh, David Kempe, Vikrant Singhal · 3 citations
Computer Science · #Machine Learning and Algorithms #Optimization and Search Problems #Algorithms and Data Compression
paper · doi:10.1145/2897518.2897656
openalex publication_date 2016/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm’s task is to identify the target by adaptively querying vertices. In response to querying a node q, the algorithm learns either that q is the target, or is given an edge out of q that lies on a shortest path from q to the target. We study this problem in a general noisy model in which each query independently receives a correct answer with probability p > 1/2 (a known constant), and an (adversarial) incorrect one with probability 1 − p.