School of Technology and Computer Science Seminars
Twenty Questions: Distributional Search Theory
by Yuval Filmus (Technion - Israel Institute of Technology)
Tuesday, January 29, 2019
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
Abstract: I’m thinking of a person in the audience. How long will it take you to find whom, using only Yes/No questions? We consider this puzzle, which underlies search theory, with a twist: I’m choosing the person according to a known distribution, and your goal is to minimize the *expected* number of questions. How does the performance of your strategy depend on the type of question you’re allowed to ask? On the type of distribution I am allowed to choose? What happens if I can lie? Joint work with Yuval Dagan (MIT), Ariel Gabizon (Zcash), Daniel Kane (UCSD), Shay Moran (IAS). |
Organised by | Prahladh Harsha |