Search using queries on indistinguishable items

Mark Braverman, Gal Oshri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 q 2 [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 k ≤ n, the optimal number of queries to attain n- (1) error probability is Θ (k3 log n). In the regime where k ≤ n, the optimal number of queries is Θ (n2k log n). 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.

Original languageEnglish (US)
Title of host publication30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013
Pages610-621
Number of pages12
DOIs
StatePublished - Dec 1 2013
Event30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013 - Kiel, Germany
Duration: Feb 27 2013Mar 2 2013

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume20
ISSN (Print)1868-8969

Other

Other30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013
CountryGermany
CityKiel
Period2/27/133/2/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Information Theory
  • Noisy Search
  • Query Complexity
  • Search

Fingerprint Dive into the research topics of 'Search using queries on indistinguishable items'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Oshri, G. (2013). Search using queries on indistinguishable items. In 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013 (pp. 610-621). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 20). https://doi.org/10.4230/LIPIcs.STACS.2013.610