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