Twenty (simple) questions
Speaker
Yuval Filmus
Technion, Israel
Host
Pritish Kamath and Akshay Degwekar
CSAIL MIT
Abstract: The game of 20 questions is a search-theoretic interpretation of entropy.
Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average. However, it might invoke arbitrary Yes/No questions.
Are there restricted sets of questions that match the optimal strategy, either exactly or approximately?
We explore this question from several different angles, uncovering a connection to binary comparison search trees, a variant of binary search trees.
Joint work with Yuval Dagan, Ariel Gabizon and Shay Moran, to appear in STOC 2017.
Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average. However, it might invoke arbitrary Yes/No questions.
Are there restricted sets of questions that match the optimal strategy, either exactly or approximately?
We explore this question from several different angles, uncovering a connection to binary comparison search trees, a variant of binary search trees.
Joint work with Yuval Dagan, Ariel Gabizon and Shay Moran, to appear in STOC 2017.