Chennai Mathematical Institute


Dr. F.C. Kohli Centre of Excellence

Perspectives in Mathematical Sciences

January 10–February 4, 2022

Monday, 10 January 2022, 19:30 IST

Avi Wigderson, Institute for Advanced Study (IAS), Princeton

Title Imitation Games (Video Recording)


One of Alan Turing's most influential papers is his 1950 Computing machinery and intelligence, in which he introduces the famous "Turing test" for probing the nature of intelligence by evaluating the abilities of machines to behave as humans. In this test, which he calls the "Imitation Game", a (human) referee has to distinguish between two (remote and separate) entities, a human and a computer, only by observing answers to a sequence of arbitrary questions to each entity.

The set-up of an imitation game is extremely versatile and powerful, and variations of it have been used throughout the theory of computation and discrete mathematics to (re)define and understand basic notions, leading to new theories and applications. I will survey several such imitation games, central to cryptography, pseudorandomness, additive combinatorics and differential privacy.

No special background is assumed.

About the speaker

Avi Wigderson photo Avi Wigderson is a distinguished Computer Scientist at the Institute of Advanced Sciences, Princeton. He has made seminal contributions to several areas of Computer science ranging from Complexity theory, Algorithms, Optimization, Randomness and Cryptography,Combinatorics and Graph theory. He has influenced the growth of these areas with his deep insights and mentored a number of PhD students and Post Doctoral Fellows who have gone on to become top researchers. He is a recipient of the Abel Prize awarded by the Norwegian Academy of Science and Letters in 2021, the Nevanlinna Prize awarded by the International Mathematical Union in 1994, the Knuth prize awarded by the Association for Computing Machinery in 2018, the Gödel prize awarded by the European Association Theoretical Computer Science and Association for Computing Machinery in 2010 and the Conant Prize of the American Mathematical Society in 2008. He delivered a plenary talk at the International Congress of Mathematicians in 2006. He is a Fellow of the ACM, a Member of the National Academy of Sciences, a Member of the American Academy of Arts and Sciences and a Member of the Norwegian Academy of Science and Letters