Dr. F.C. Kohli Centre of ExcellencePerspectives in Mathematical SciencesJanuary 10–February 4, 2022Monday, 10 January 2022, 19:30 ISTAvi Wigderson, Institute for Advanced Study (IAS), PrincetonTitle Imitation Games (Video Recording) Abstract 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 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
