Dr. habil. Benjamin Doerr, MPI, Room 304
Christian Klein, MPI, Room 321

Seminar: Liar Games and Noisy Channels [summer 2006]

Topic

Liar Games are an interesting subject for discrete mathematicians, game theorists and computer scientists. A simple (?) problem in this context is known as Ulam's liar game: Carole thinks of a number between one and a million. Paul tries to guess it using yes/no questions only. The catch is that Carole may lie one time. Of course, she does not tell which question she answered wrongfully. How many questions does Paul need to determine the number? Besides the natural appeal games have, computer scientists use these games to model so-called noisy channels. By `noisy' we mean that sender sending a one does not always mean that receiver actually receives a one (but may-be a zero instead).

Audience, Prerequisites, etc.

In the seminar we explore the area of liar games and their applications. It counts as 'seminar' for both computer science and mathematics students. Understanding of the basics in mathematics is required.

Time, Location

All talks take place in the MPII building, Room 024.

Fr. 19.05.2006	16:00 - 17:15	Michaela
	17:15 - 18:30	Bettina
Mo. 29.05.2006	18:00 - 19:15	Irina
	19:15 - 20:30	Olaf
Mi. 31.05.2006	18:00 - 19:15	Vasilis
	19:15 - 20:30	Andreas
Mo. 26.06.2006	18:00 - 19:15	Christian
Mi. 28.06.2006	18:00 - 19:15	Roxana
	19:15 - 20:30	Andrea

References

Contact

In case of questions, come by and ask or send an email!

PS: You can't wait that long? Think about this one: Professor Paul has a group consisting of 15 beginners, 4 bachelor student, 3 master students, one PhD student, no PostDoc and no Privatdozent [a German group, as you can see]. Each year, he makes a list of people proposed for promotion. Promotion means that a beginner becomes a bachelor student, a bachelor student becomes a master student and so on. If a Privatdozent is promoted, he gets tenures, which is the ultimate aim.

Faced with Pauls list of promotion proposals, Dean Carole has two options. She can accept the list. In this case, all people on the list are promoted, and all others are fired [OK, some US flavor in the game as well]. Or, she can refuse the list, in which case the people not on the list are promoted and those on the list are fired.

Paul wins the game, if at least one of his people gets tenures. Can Paul win the game? What, if group members instead of being fired are only degraded to a beginners level? What is the solution for a general set-up of the game?

PPS: You are tired of problems that were already solved? [Not that this would be the full truth for the tenure game.] No problem. I have some cool topics for bachelor, master, diploma and PhD theses. Drop in my office and I'll tell you more.

Last modified: Tue Apr 25 15:13:53 CEST 2006