Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 20, 2010, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Johannes Lengler (Uni Saarbrücken)
A Liar Game is a game between two adversary players, Paul and Carole. The basic variant is as follows. Carole chooses secretly one out of n coins. Now Paul may ask arbitrary YES-/NO-questions. Carole must answer his questions, but she is allowed to lie at most k times. We are interested in the minimal number of questions that Paul needs in order to find out Carole's secret.
I will briefly mention some variants of Liar Games and show how they can be modelled in the general framework of Automata Liar Games. I will present formal weight functions as the main tool for studying such games. Finally, I will show that this approach solves the game exactly for a rich class of Liar Games, for large n.
Automatic MiSe System Software Version 1.4803M | admin login