Yuval Filmus, Technion, Haifa, Israel
Description
Combinatorics and Theoretical Computer Science seminar.
Speaker: Yuval Filmus.
Affiliation: Technion, Haifa, Israel.
Date and Time: Monday 25 February, 3.00pm - 4.00pm.
Venue: Ramanujan Hall, Mathematics Department, IIT Bombay.
Title: Twenty Questions: Distributional Search Theory.
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).