License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2013.610
URN: urn:nbn:de:0030-drops-39696
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3969/
Go to the corresponding LIPIcs Volume Portal

Braverman, Mark ; Oshri, Gal

Search using queries on indistinguishable items

pdf-format:
57.pdf (0.6 MB)

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 \in [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^{-Omega(1)} error probability is Theta(k^3 log n). In the regime where k > n, the optimal number of queries is Theta(n^2 k 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.

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2013:3969,
  author =	{Mark Braverman and Gal Oshri},
  title =	{{Search using queries on indistinguishable items}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{610--621},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3969},
  URN =		{urn:nbn:de:0030-drops-39696},
  doi =		{10.4230/LIPIcs.STACS.2013.610},
  annote =	{Keywords: Search, Noisy Search, Information Theory, Query Complexity}
}

Keywords: Search, Noisy Search, Information Theory, Query Complexity
Collection: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue Date: 2013
Date of publication: 26.02.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI