SPEAKER: Ronald Graham
UC San Diego (CSE)
We discuss various mathematical and algorithmic aspects of a variant of the familiar "20 questions" problem. In this version, we are trying to learn as much as we can about a set of k > 1 secrets held by an adversary. We are only allowed to ask binary (= yes/no) questions, and the adversary must answer truthfully. We will show how these questions relate to classic results of Erdos and Lovasz on hypergraphs, as well as to more recent coding theory results of Alon and others. This problem arose in connection with certain Internet caching and routing algorithms (as mentioned in last week's talk by Bruce Maggs of Akamai).