Tata Institute of Fundamental Research
Twenty Questions: Distributional Search Theory
STCS Colloquium
Speaker:
Yuval Filmus (Technion - Israel Institute of Technology
Department of Computer Science
Israel)
Organiser:
Prahladh Harsha
Date:
Tuesday, 29 Jan 2019, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Yuval Filmus (Technion - Israel Institute of Technology Department of Computer Science Israel) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 29 Jan 2019, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).