TY - GEN

T1 - On optimal strategies for searching in presence of errors

AU - Muthukrishnan, S.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028251792&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028251792&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028251792

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 680

EP - 689

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -