Yuval Filmus – Twenty (simple) questions

Event Details

  • Date:

Huffman coding has a search-theoretic interpretation as the optimal strategy for the twenty questions game.
In this game, Alice chooses x ∈ {1,…,n} according to a distribution µ, and Bob identifies x using yes/no questions.
Bob’s goal is to use the minimum number of questions in expectation.
A strategy for Bob corresponds to a prefix code for {1,…,n}, and this shows that Bob’s optimal strategy uses a Huffman code for µ.
However, this strategy could use arbitrary yes/no questions.
What happens when we restrict the set of yes/no questions that Bob is allowed to use?
Joint work with Yuval Dagan, Ariel Gabizon, and Shay Moran.