Playing with cards and hats - data transmission and coding theory
(F. C. Kohli Auditorium, KReSIT Building, 5:30 pm, Friday, Jan 4, 2008.)
|About the talk:|
Given 16 playing cards, if you select one of them, then with 4 questions I can deduce from your answers of yes/no type which card you choose. With one more question I shall detect if one of your answer is not compatible with the others, but I shall not be able to correct it. The earliest error correcting code, due to Richard Hamming (1950), shows that 7 questions suffice (and this is optimal).
Seven people are in a room, each has a hat on his head, the color of which is black or white. Hat colors are chosen randomly. Everybody sees the color of the hat on everyone's head, but not on their own. People do not communicate with each other. Everyone gets to guess (by writing on a piece of paper) the color of their hat. They may write: Black/White/Abstain. The people in the room win together or lose together. The team wins if at least one of the three people did not abstain, and everyone who did not abstain guessed the color of their hat correctly. How will this team decide a good strategy with a high probability of winning? Again the answer is given by Hammings code, and the probability of winning for the team is 7/8.
Before tossing a coin 7 consecutive time, you want to make a limited number of bets and be sure that one of them will have at most one wrong answer. How many bets are required? Once more the answer is given by Hamming and it is 16.
After a discussion of these three examples we shall give a brief survey of coding theory, up to the more recent codes involving algebraic geometry.
About the Speaker:
Michel Waldschmidt graduated from the University of Nancy in 1968. He obtained his PhD from the University of Bordeaux I in 1972. He is currently a Professor at Paris VI (Université Pierre et Marie Curie) since 1973. His work deals with number theory: his main interest is in transcendental numbers and Diophantine approximation. He has solved several open questions and has more than 150 publications on this field, including a few books. He has received the Médaille Albert Chatelet in 1974, and the Silver Medal of CNRS in 1978. He was awarded the Prix Marquet by the French Academy of Sciences in 1980 and he received the Distinguished Award of the Hardy-Ramanujan Society in 1986. He has had many research students, several of them being now among the best experts in their field. He was President of the French Mathematical Society (SMF) from 2001 to 2004, and in 2005 he became Vice-President of the CIMPA (International Center of Pure and Applied Mathematics - created 25 years ago under a UNESCO recommendation). For many years he has been a coordinator of collaborations in mathematics between France and India. He is involved in several international cooperation projects, especially with south-east Asian countries. He is a member of several editorial boards, including the Ramanujan Journal of Mathematics, as well as a member of several international advisory committees, including the selection panel for the 2006 and 2007 SASTRA Ramanujan Prize Committee.