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

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

event speaker icon
עידן מהלל (הרצאה סמינריונית למגיסטר)
event date icon
יום רביעי, 25.11.2020, 12:30
event location icon
Zoom, Meeting ID: 954 7347 4134, Password: 32000
event speaker icon
מנחה: 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".