Seminario Interdipartimentale di Algoritmica
 
 
 

Lunedì 20 Novembre 2000  ore 12:00
On the game of ``Twenty Questions'' with a liar
Prof. Peter Gacs
CS Department, Boston University

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract:
Consider a version of the game ``Twenty Questions'' played on the set {1,...,N} where the player giving answers may lie in her answers. For some fixed and previously known fraction r, the questioner will make Q questions (he must announce his chosen value of Q in advance) and the responder may lie in up to rQ of the answers. It is not obvious that there is any Q(N,r) allowing the questioner to win, even with r < 1/100000 (the reader should try to find a strategy, even with 2^N/r questions). The talk will solve this problem and will connect it to related problems.