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.