Epa, Narthana S. ;
Gan, Junhao ;
Wirth, Anthony
ResultSensitive Binary Search with Noisy Information
Abstract
We describe new algorithms for the predecessor problem in the Noisy Comparison Model. In this problem, given a sorted list L of n (distinct) elements and a query q, we seek the predecessor of q in L: denoted by u, the largest element less than or equal to q. In the Noisy Comparison Model, the result of a comparison between two elements is nondeterministic. Moreover, multiple comparisons of the same pair of elements might have different results: each is generated independently, and is correct with probability p > 1/2. Given an overall error tolerance Q, the cost of an algorithm is measured by the total number of noisy comparisons; these must guarantee the predecessor is returned with probability at least 1  Q. Feige et al. showed that predecessor queries can be answered by a modified binary search with Theta(log (n/Q)) noisy comparisons.
We design resultsensitive algorithms for answering predecessor queries. The query cost is related to the index, k, of the predecessor u in L. Our first algorithm answers predecessor queries with O(log ((log^{*(c)} n)/Q) + log (k/Q)) noisy comparisons, for an arbitrarily large constant c. The function log^{*(c)} n iterates c times the iteratedlogarithm function, log^* n. Our second algorithm is a genuinely resultsensitive algorithm whose expected query cost is bounded by O(log (k/Q)), and is guaranteed to terminate after at most O(log((log n)/Q)) noisy comparisons.
Our results strictly improve the stateoftheart bounds when k is in omega(1) intersected with o(n^epsilon), where epsilon > 0 is some constant. Moreover, we show that our resultsensitive algorithms immediately improve not only predecessorquery algorithms, but also binarysearchlike algorithms for solving key applications.
BibTeX  Entry
@InProceedings{epa_et_al:LIPIcs:2019:11556,
author = {Narthana S. Epa and Junhao Gan and Anthony Wirth},
title = {{ResultSensitive Binary Search with Noisy Information}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {60:160:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11556},
URN = {urn:nbn:de:0030drops115568},
doi = {10.4230/LIPIcs.ISAAC.2019.60},
annote = {Keywords: Faulttolerant search, random walks, noisy comparisons, predecessor queries}
}
28.11.2019
Keywords: 

Faulttolerant search, random walks, noisy comparisons, predecessor queries 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 