Application: Searching with lies

In Stanislaw Ulam's 1976 autobiography [U] (and, in a completely different form, in Elwyn Berlekamp's 1964 PhD thesis [B]), one finds the following problem concerning two players playing a generalization of the childhood game of ``20 questions''. PROBLEM Player 1 secretly chooses a number from $1$ to $M$ ($M$ is large but fixed). Player 2 asks a series of ``yes/no questions'' in an attempt to determine that number. Player 1 may lie at most $e$ times ($e\geq 0$ is fixed). What is the minimum number of ``yes/no questions'' Player 2 must ask to (always) be able to correctly determine the number Player 1 chose?

Definition 3.6.1   If answers between successive questions (``feedback'') is allowed, call this minimum number of ``yes/no questions'' player 2 must ask, $f(M,e)$. If feedback is not allowed, call this minimum number $g(M,e)$.

Clearly,

$$f(M,e)\leq g(M,e).$$

We shall only discuss the non-feedback case and shall not mention $f(M,e)$ further. In practice, we not only want to know $g(M,e)$ but an efficient algorithm for determining the ``yes/no questions'' Player 2 should ask. In the feedback allowed case, Berlekamp was concerned with a discrete analog of a problem which arises when trying to design a analog-to-digital converter for sound recording which compensates for possible feedback.

Lemma 3.6.2   Fix any $e$ and $M$. $g(M,e)$ is the smallest $n$ such that $A_2(n,2e+1)\geq M$.

We shall not prove this here. Record the $n$ answers to the ``yes/no questions'' as an $n$-tuple of 0's (for ``no'') and $1$'s (for ``yes''). The binary code $C$ is the set of all codewords corresponding to correct answers. It is known that if a binary code $C\subset \mathbb{F}_2^n$ is $e$-error correcting then $\vert C\vert\leq A_2(n,2e+1)$. We want the smallest possible $n$ satisfying this condition. The above-mentioned fact allows us to reduce the problem of determining the solution to the seaching with lies without feedback to the (very hard) problem below. PROBLEM Determine $A_2(n,d)$ for all $n,d$. As we already mentioned, this is perhaps the central problem in coding theory and is unknown for most $n>30$. In addition, of course one would also like constructive fact encoding and decoding procedures for the code $C\subset \mathbb{F}_2^n$ such that $\vert C\vert= A_2(n,2e+1)$. More discussion on the searching with lies problem will be given in the next section, after more background material has been introduced.