Noisy (Binary) Searching: Simple, Fast and Correct
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515371" target="_blank" >RIV/00216208:11320/25:10515371 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.STACS.2025.29" target="_blank" >https://doi.org/10.4230/LIPIcs.STACS.2025.29</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2025.29" target="_blank" >10.4230/LIPIcs.STACS.2025.29</a>
Alternative languages
Result language
angličtina
Original language name
Noisy (Binary) Searching: Simple, Fast and Correct
Original language description
This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter p that dictates that a comparison can be incorrect with probability p, independently of other queries. We state two types of upper bounds on the number of queries: the worst-case and expected query complexity scenarios. The bounds improve the ones known to date, i.e., our algorithms require fewer queries. Additionally, they have simpler statements, and work for the full range of parameters. All query complexities for the expected query scenarios are tight up to lower order terms. For the problem where the target prior is uniform over all possible inputs, we provide an algorithm with expected complexity upperbounded by (log<inf>2</inf> n + log<inf>2</inf> δ<sup>-1</sup> + 3)/I(p), where n is the domain size, 0 <= p < 1/2 is the noise ratio, and δ > 0 is the failure probability, and I(p) is the information gain function. As a side-effect, we close some correctness issues regarding previous work. Also, en route, we obtain new and improved query complexities for the search generalized to arbitrary graphs. This paper continues and improves the lines of research of Burnashev-Zigangirov [Prob. Per. Informatsii, 1974], Ben-Or and Hassidim [FOCS 2008], Gu and Xu [STOC 2023], and Emamjomeh-Zadeh et al. [STOC 2016], Dereniowski et al. [SOSA@SODA 2019].
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/LL2406" target="_blank" >LL2406: Robust Streaming Algorithms versus Adaptive Adversaries</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Leibniz International Proceedings in Informatics Lipics
ISBN
978-3-95977-365-2
ISSN
—
e-ISSN
—
Number of pages
18
Pages from-to
29.1-29.18
Publisher name
Schloss Dagstuhl - Leibniz Center for Informatics
Place of publication
Dagstuhl
Event location
Jena, Germany
Event date
Mar 4, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001532683200029