How to Play a Guessing Game with Full and Half Liars?

Wednesday, May 2, 2001 - 17:30
TH 331
Bala Ravikumar San Francisco State University

Player A guesses an integer between 1 and n. Player B is required to find the guess by querying A with yes or no answer. If A answers B's queries truthfully, binary search is the best strategy for A. We will consider several variations of this problem when A's is allowed to lie in various ways. This problem has been extensively studied for about 20 years since it was raised in the autobiography of the Polish mathematician Ulam and has potential applications in fault-tolerant distributed computing. After surveying old results, we will present some new results on this problem.