About the series
Bio: Avi Wigderson is the Herbert H. Maass Professor in the School of Mathematics at the Institute for Advanced Study. Wigderson earned his Ph.D. from Princeton University in 1983.
His research covers many aspects of computational complexity theory and its interactions with mathematics, including randomness and pseudorandomness; algorithms and optimization; circuit and proof complexity; quantum computation and communication; and cryptography.
Professor Wigderson has received many awards for his work in the field including the 2021 Abel Prize, Knuth Prize, Gödel Prize, Conant Prize, and Nevanlinna Prize. He is also a member of the American Academy of Arts and Sciences, the National Academy of Science, and the Norwegian Academy of Science and Letters.
Talk 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.
This lecture will exposit, through examples from a surprisingly diverse array of settings, the remarkable power of this basic idea to understand many other concepts. I will discuss variations of the Imitation Game in which we change the nature of the referee, and of the objects to be distinguished, to yield different analogs of the Turing test. These new Imitation Games lead to novel, precise, and operative definitions of classical notions, including secret, knowledge, privacy, randomness, proof, fairness, and others. These definitions have in turn led to numerous results, applications, and understanding.
Some, among many consequences of this fundamental paradigm, are the foundations of cryptography, the surprising discoveries on the power and limits of randomness, the recent influential notion of differential privacy, and breakthrough results on patterns in the prime numbers and navigation in networks. Central to each of these settings are computational and information theoretic limitations placed on the referee in the relevant Imitation Game.
This lecture will survey some of these developments and speculate on future uses of this paradigm in science and society, in a way which is hopefully accessible without any specific background knowledge.
Register in advance for this webinar:
https://nsf.zoomgov.com/webinar/register/WN_ilRroirAQzyLlNj7bSoESQ
Or an H.323/SIP room system:
H.323: 161.199.138.10 (US West) or 161.199.136.10 (US East)
Meeting ID: 160 495 1246
Passcode: 009446
SIP: 1604951246@sip.zoomgov.com
Passcode: 009446
After registering, you will receive a confirmation email containing information about joining the webinar.
