Talks
Spring 2017 # Twenty (Simple) Questions (and Hitting Maximal Antichains)

Thursday, April 13th, 2017 4:00 pm4:30 pm

A basic combinatorial interpretation of Shannon's entropy function is via the 20 questions'' game.
This cooperative game is played by two players, Alice and Bob:
Alice picks a distribution $\pi$ over the numbers $\{1,\ldots,n\}$,
and announces it to Bob.
She then chooses a number $x$ according to $\pi$,
and Bob attempts to identify $x$ using as few
Yes/No queries as possible, on average.

An optimal strategy for the 20 questions'' game is given by a Huffman code for $\pi$:
Bob's questions reveal the codeword for $x$ bit by bit.
This strategy finds $x$ using fewer than $H(\pi)+1$ questions on average.
However, the questions asked by Bob could be arbitrary.
In this paper, we investigate the following question:
\emph{Are there restricted sets of questions that match the performance of Huffman codes, either exactly or approximately?}

Our first main result shows that for every distribution $\pi$,
Bob has a strategy that uses only questions of the form $x < c$?'' and $x = c$?'’,
and uncovers $x$ using at most $H(\pi)+1$ questions on average,
matching the performance of Huffman codes in this sense.
We also give a natural set of $O(rn^{1/r})$ questions that achieve a performance of at most $H(\pi)+r$,
and show that $\Omega(rn^{1/r})$ questions are required to achieve such a guarantee.

Our second main result gives a set $\Q$ of $1.25^{n+o(n)}$ questions such that
for every distribution $\pi$, Bob can implement an \emph{optimal} strategy for $\pi$ using only questions from $\cQ$.
We also show that $1.25^{n-o(n)}$ questions are needed, for infinitely many $n$.
Here, the set $\Q$ is derived via a random construction.
If time will allow, we will discuss the challenge of derandomizing
this construction, and a connection with hitting maximal antichains.

Based on joint work with Yuval Dagan, Yuval Filmus, and Ariel Gabizon