## Abstract

We design efficient competitive algorithms for discovering information hidden by an adversary. Specifically, consider a game in a given interval grpah*G*in which the adversary chooses an independent set

*X*in

*G*. Our ogal is to discover this hidden independent set

*X*by making the fewest queries of the form "Is point

*p*covered by an interval in

*X*?" Our interest in this problem stems from two applications: experimental gene discovery with PCR tehcnology and the game of Battleship (in a

*1*-dimensional setting). We prove adaptive algorithms for both the verification scenario (given an independent set, is it

*X*?) and the discovery scenario (find

*X*without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.