Skip to main content

Search using queries on indistinguishable items

Author(s): Braverman, Mark; Oshri, G

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorOshri, G-
dc.identifier.citationBraverman, M, Oshri, G. (2013). Search using queries on indistinguishable items. 20 (610 - 621. doi:10.4230/LIPIcs.STACS.2013.610en_US
dc.description.abstractWe 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.en_US
dc.format.extent610 - 621en_US
dc.relation.ispartof30th International Symposium on Theoretical Aspects of Computer Scienceen_US
dc.rightsAuthor's manuscripten_US
dc.titleSearch using queries on indistinguishable itemsen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
Search using queries on indistinguishable items.pdf353.49 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.