דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
יובל פילמוס (מדעי המחשב, טכניון)
event date icon
יום ראשון, 26.03.2017, 12:30
event location icon
טאוב 601
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.