An Almost Optimal Algorithm for Unbounded Search with Noisy Information
Loading...
Citations
Scopus:
Altmetric:
Altmetric::
Download
Associated Records
File Licence
Date
2022-06-29
Source Title
Leibniz International Proceedings in Informatics
Journal Title
Journal ISSN
Volume Title
Publisher
Dagstuhl Publishing
Melbourne Authors
Affiliation
Computing and Information Systems
Document Type
Conference Paper
Subject Code
Citation
Gan, J., Wirth, A. & Zhang, X. (2022). An Almost Optimal Algorithm for Unbounded Search with Noisy Information. Czuma, A (Ed.) Xin, Q (Ed.) Leibniz International Proceedings in Informatics, 227, pp.25:1-25:15. Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SWAT.2022.25.
Access Status
Open Access
Access URL
Open Access URL
Open Access at PMC
Linked Resource URL
NHMRC Grant Code
ARC Grant Code
Description
Abstract
Given a sequence of integers, š® = sā, sā,ā¦ in ascending order, called the search domain, and an integer t, called the target, the predecessor problem asks for the target index N such that s_N is the largest integer in š® satisfying s_N ā¤ t. We consider solving the predecessor problem with the least number of queries to a binary comparison oracle. For each query index i, the oracle returns whether s_i ā¤ t or s_i > t. In particular, we study the predecessor problem under the UnboundedNoisy setting, where (i) the search domain š® is unbounded, i.e., n = |š®| is unknown or infinite, and (ii) the binary comparison oracle is noisy. We denote the former setting by Unbounded and the latter by Noisy. In Noisy, the oracle, for each query, independently returns a wrong answer with a fixed constant probability 0 < p < 1/2. In particular, even for two queries on the same index i, the answers from the oracle may be different. Furthermore, with a noisy oracle, the goal is to correctly return the target index with probability at least 1- Q, where 0 < Q < 1/2 is the failure probability.
Our first result is an algorithm, called NoS, for Noisy that improves the previous result by Ben-Or and Hassidim [FOCS 2008] from an expected query complexity bound to a worst-case bound. We also achieve an expected query complexity bound, whose leading term has an optimal constant factor, matching the lower bound of Ben-Or and Hassidim. Building on NoS, we propose our NoSU algorithm, which correctly solves the predecessor problem in the UnboundedNoisy setting. We prove that the query complexity of NoSU is ā_{i = 1}^k (log^{(i)} N) /(1-H(p))+ o(log N) when log Q^{-1} ā o(log N), where N is the target index, k = log^* N, the iterated logarithm, and H(p) is the entropy function. This improves the previous bound of O(log (N/Q) / (1-H(p))) by reducing the coefficient of the leading term from a large constant to 1. Moreover, we show that this upper bound can be further improved to (1 - Q) ā_{i = 1}^k (log^{(i)} N) /(1-H(p))+ o(log N) in expectation, with the constant in the leading term reduced to 1 - Q. Finally, we show that an information-theoretic lower bound on the expected query cost of the predecessor problem in UnboundedNoisy is at least (1 - Q)(ā_{i = 1}^k log^{(i)} N - 2k)/(1-H(p)) - 10. This implies the constant factor in the leading term of our expected upper bound is indeed optimal.