MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Coping with Liars in Searching Procedures

par Ugo Vaccaro


Date :04/03/10
Time :14h
Location :Euler Violet


What's the minimum number of questions needed to find an unknown number x,
if up to e of the answers may be erroneous/mendacious?
The basic version of this problem, in which questions admit yes/no answers,
was originally posed by the hungarian mathematician A. Renyi in the 60's
and successively popularized by the polish mathematician S. Ulam
in its widely read autobiography "Adventures of a Mathematician", Scribner,
New York, 1976.

The general scenario is that of a game between two players, the Questioner
and the Responder, in which, before starting to play, both
players agree on:
1. a set of objects, called the search space, and the number n of questions,
2. some kind of limitation on the way the Responder is allowed to lie,
3. the format of questions,
4. the degree of interactivity between players.

In recent years the problem has been extensively studied and greatly
generalized.
Most of the efforts have been towards achieving two goals:
a) extending the classical results to more general format of questions
b) reducing the interaction between the Questioner and the Responder

In this talk I shall present the basic results in the area as well as
some new results on above two issues that are, to date, the best known.





Page des séminaires