Noisy Search with Comparative Feedback
This addresses a theoretical search problem with variable noise, providing foundational insights for algorithms in noisy environments, though it is incremental in nature.
The paper tackles the problem of noisy search with comparative feedback where noise varies with distance to the target, showing that a target among n items can be found in O(log n) queries and revealing a speedup of only log log k for k possible answers per query, contrary to the expected log k.
We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases.