On optimal strategies for searching in presence of errors

S. Muthukrishnan

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

    Abstract

    We consider the following game between Paul and Carole modeling the problem of searching a discrete domain in presence of errors. Paul searches for an unknown element e in a set S of n elements using w queries. Each query is a partition of S into q parts. Carole is the Oracle who in response to each query points out the part containing e. She is permitted to lie, though not more than k times. We provide a strategy for Paul to determine the unknown element using at most one query more than that necessary against an adversarial Carole. Our result holds for k, the maximum number of lies, nearly doubly logarithmic in w, the total number of queries. Previous results either work for a fixed k and/or use a constant multiplicative factor more queries than that needed. Our work involves the analysis of a related chip game. Our exposition here is in terms of the classical defective coins problem which is that of identifying the single defective coin from amongst n coins using an equal arms balance. The defective coin is heavier than the others, all of which are of equal weight. This problem is the q - way search problem above for q = 3.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
    PublisherPubl by ACM
    Pages680-689
    Number of pages10
    ISBN (Print)0898713293
    StatePublished - 1994
    EventProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms - Arlington, VA, USA
    Duration: Jan 23 1994Jan 25 1994

    Publication series

    NameProceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

    Other

    OtherProceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms
    CityArlington, VA, USA
    Period1/23/941/25/94

    ASJC Scopus subject areas

    • Software
    • Mathematics(all)

    Fingerprint

    Dive into the research topics of 'On optimal strategies for searching in presence of errors'. Together they form a unique fingerprint.

    Cite this