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 BenOr and Hassidim [FOCS 2008] from an expected query complexity bound to a worstcase bound. We also achieve an expected query complexity bound, whose leading term has an optimal constant factor, matching the lower bound of BenOr 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) /(1H(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) / (1H(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) /(1H(p))+ o(log N) in expectation, with the constant in the leading term reduced to 1  Q. Finally, we show that an informationtheoretic 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)/(1H(p))  10. This implies the constant factor in the leading term of our expected upper bound is indeed optimal.
BibTeX  Entry
@InProceedings{gan_et_al:LIPIcs.SWAT.2022.25,
author = {Gan, Junhao and Wirth, Anthony and Zhang, Xin},
title = {{An Almost Optimal Algorithm for Unbounded Search with Noisy Information}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {25:125:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772365},
ISSN = {18688969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16185},
URN = {urn:nbn:de:0030drops161854},
doi = {10.4230/LIPIcs.SWAT.2022.25},
annote = {Keywords: Faulttolerant search, noisy binary search, query complexity}
}
Keywords: 

Faulttolerant search, noisy binary search, query complexity 
Collection: 

18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) 
Issue Date: 

2022 
Date of publication: 

22.06.2022 