Yuval Filmus: Twenty (simple) questions

Thursday, March 2, 2017 - 4:00pm to 5:00pm
Location: 
32-G575
Speaker: 
Yuval Filmus
Biography: 
Technion, Israel
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.