Noisy (Binary) Searching: Simple, Fast and Correct

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Noisy (Binary) Searching: Simple, Fast and Correct

Popis výsledku v původním jazyce

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&lt;inf&gt;2&lt;/inf&gt; n + log&lt;inf&gt;2&lt;/inf&gt; δ&lt;sup&gt;-1&lt;/sup&gt; + 3)/I(p), where n is the domain size, 0 &lt;= p &lt; 1/2 is the noise ratio, and δ &gt; 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].

Název v anglickém jazyce

Noisy (Binary) Searching: Simple, Fast and Correct

Popis výsledku anglicky

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&lt;inf&gt;2&lt;/inf&gt; n + log&lt;inf&gt;2&lt;/inf&gt; δ&lt;sup&gt;-1&lt;/sup&gt; + 3)/I(p), where n is the domain size, 0 &lt;= p &lt; 1/2 is the noise ratio, and δ &gt; 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].

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LL2406" target="_blank" >LL2406: Robustní proudové algoritmy versus adaptivní protivníci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Leibniz International Proceedings in Informatics Lipics

ISBN

978-3-95977-365-2

ISSN

—

e-ISSN

—

Počet stran výsledku

18

Strana od-do

29.1-29.18

Název nakladatele

Schloss Dagstuhl - Leibniz Center for Informatics

Místo vydání

Dagstuhl

Místo konání akce

Jena, Germany

Datum konání akce

4. 3. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001532683200029