EE Seminar: Reducing Guesswork via an Unreliable Oracle
Speaker: Amir Burin
M.Sc. student under the supervision of Dr. Ofer Shayevitz
Sunday, June 18th, 2017 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering
Reducing Guesswork via an Unreliable Oracle
The problem of guessing random variables has many different implications in coding theory, information theory, cryptography and discrete searching and sorting algorithms. Usually, one is interested in the minimal expected number of guesses required to correctly guess a realization of a random variable. In this work, we consider the case where prior to guessing, the guesser has access to an all-knowing but possibly malicious oracle that allows him to ask a binary question of his choosing. We are interested in the most useful question the guesser can ask in terms of reducing his expected number of guesses, as well as in the associated reduction in guesswork.
Specifically, we consider the following setup. Alice holds an r.v. X, and Bob is trying to guess its value by asking questions of the form ``is X=x?''. Alice answers truthfully and the game terminates once Bob guesses correctly. Before the game begins, Bob is allowed to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a question of the form ``is X in A?''. Carole is known to lie with a given probability 0≤p≤1/2. What should Bob ask Carole if he would like to minimize his expected guessing time?
When Carole is truthful (p=0), it is easy to show that Bob should order the symbol probabilities in descending order, and ask Carole whether the index of X w.r.t. this order is even or odd. We show that this strategy is almost optimal for any lying probability p, up to a small additive constant upper bounded by a 1/4.
