Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

High quality sets of questions in the "20 Questions" game
event speaker icon
Idan Mehalel (M.Sc. Thesis Seminar)
event date icon
Wednesday, 25.11.2020, 12:30
event location icon
Zoom, Meeting ID: 954 7347 4134, Password: 32000
event speaker icon
Advisor: Prof. Yuval Filmus
In the "20 questions" game Alice picks a probability distribution over the set {1,...,n}, and draws a secret element x from it. Bob's goal is to construct a strategy to reveal x using only "Yes or No" questions, while minimizing the expected number of questions asked. Bob's success is guaranteed if he uses Huffman code, but then he might ask any possible question. In the paper "Twenty (simple) questions", Dagan et al. showed that the minimal number of questions which allows to construct optimal strategies for all distributions, denoted q(n), is much smaller than the number of all questions. They provide lower and upper bounds on q(n) for any n, but calculate it exactly only for some n values. We give a formula for the value of q(n) for any n, and present a new explicit lower bound on q(n). We also generalize some results of Dagan et al. to the "d-ary 20 questions" game, in which every question has d>1 possible answers, instead of only "Yes" and "No".