Search using queries on indistinguishable items

DOI10.4230/LIPICS.STACS.2013.610MaRDI QIDQ2957922zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Gal Oshri

Publication date 30 January 2017

Full work available at URL https://arxiv.org/abs/1302.0892

zbMATH Keywords

information theorynoisy searchquery complexitysearch

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: We investigate the problem of determining a set S of k indistinguishable integers in the range [1,n]. The algorithm is allowed to query an integer $qin[1,n]$, and receive a response comparing this integer to an integer randomly chosen from S. The algorithm has no control over which element of S the query q is compared to. We show tight bounds for this problem. In particular, we show that in the natural regime where $klen$, the optimal number of queries to attain $n^{-Omega(1)}$ error probability is $Theta(k^{3}logn)$. In the regime where $k>n$, the optimal number of queries is $Theta(n^{2}klogn)$. Our main technical tools include the use of information theory to derive the lower bounds, and the application of noisy binary search in the spirit of Feige, Raghavan, Peleg, and Upfal (1994). In particular, our lower bound technique is likely to be applicable in other situations that involve search under uncertainty.

Recommendations

• Searching with known error probability
• Algorithms and Computation
• Perfect minimally adaptive \(q\)-ary search with unreliable tests
• Binary search with errors and variable cost queries
• Coping with errors in binary search procedures (Preliminary Report)

Cited in

(2)

• How many random questions are necessary to identify n distinct objects?
• The parity search problem

This page was built for publication: Search using queries on indistinguishable items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957922)