Twenty (simple) questions

Speaker: Yuval Filmus , Technion, Israel

Date: Thursday, March 02, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Yuval Filmus:Twenty (simple) questions

Abstract: The game of 20 questions is a search-theoretic interpretation of entropy.
Alice chooses a number x in {1,...,n} according to a known distribution \mu, and Bob identifies x using Yes/No questions. Bob's goal is to minimize the expected number of questions until x is identified, and his optimal strategy uses about H(\mu) questions on average. However, it might invoke arbitrary Yes/No questions.

Are there restricted sets of questions that match the optimal strategy, either exactly or approximately?

We explore this question from several different angles, uncovering a connection to binary comparison search trees, a variant of binary search trees.

Joint work with Yuval Dagan, Ariel Gabizon and Shay Moran, to appear in STOC 2017.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar at Wednesday, February 22, 2017 at 6:59 PM.