|
|
|
Abstract: We consider a 2-person perfect information "liar" game, often called a Renyi-Ulam game. The basic game is that of "twenty questions" played between questioner Paul and responder Carole. Paul searches for a distinguished element x in a search space [n] by asking Yes-No questions of the form "is x in A", where A is a subset of n. Carole responds "Yes" or "No", lying in up to some bounded number of responses. If Paul's questions are all offline, this is equivalent to block coding, but we allow adaptivity when Paul may choose each question based on Carole's previous answers. We survey several results and techniques for the adaptive game, including the general case in which Carole's pattern of lying is constrained to come from a bounded set. The talk will include joint work with Catherine Yan, Vadim Ponomarenko, and Kathryn Nyman.
|
