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)
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