Pauli Lectures 2012
The Wolfgang Pauli Lectures 2012 were dedicated to mathematics.
Prof. Avi Wigderson
Institute for Advanced Study, Princeton, USA
Avi Wigderson is a professor of Mathematics at the Institute for Advanced Study in Princeton. After studying Computer Science at Technion in Haifa, he obtained his PhD in 1983 from Princeton University. He held then various visiting positions including IBM Research at San Jose, MSRI Berkeley, and IAS Princeton. From 1986 to 2003 he was associate professor at the Hebrew University in Jerusalem. Wigderson has been for two decades a leading figure in the field of Mathematics of Computer Science, with fundamental contributions, in particular in Complexity Theory, Randomness, and Cryptography. He has been invited speaker at ICM in Tokyo (1990), and Zurich (1994), and plenary speaker in Madrid (2006). Among many awards he received both the Nevanlinna Prize (1994), and the Gödel Prize (2009).
The Computational Lens
The advent of computation theory, followed by computing practice, has completely revolutionized our lives. Computational complexity theory, studying the power and limits of computing systems provides the mathematical foundations of computer science and technology. Its investigations has not only led to advances in a variety of computer-related applications, but also to better understanding of other disciplines, including mathematics and the sciences. Common objects of study in these vast fields often reveal new facets when viewed through the computational lens. In this series of three lectures I plan to explain some central aspects of this extensive theory, and their consequences and challenges. The talks are aimed at a general public - no specific technical knowledge will be assumed. Moreover, each lecture is independent of the others. This series is dedicated to Alan Turing, the father of computing, on the 100 anniversary of his birth.
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits to Human
Monday, May 7, 2012, 20:15 h Auditorium Maximum, HG F 30
The "P vs. NP" problem, formulated by computer theorists in the 1970s, quickly became a central outstanding problem of science and mathematics. In this talk I will attempt to describe its mathematical, scientific and philosophical content. I will discuss its status, and the implications of its resolution on science and technology (making clear that the $1M prize on solving it pales in comparison with these implications). No special background will be assumed.
Cryptography: Secrets and Lies, Knowledge and Trust
Tuesday, May 8, 2012, 20:15 h Auditorium Maximum, HG F 30
What protects your computer password when you log on, or your credit card number when you shop on-line, from hackers listening on the communication lines? Can two people who never met create a secret language in the presence of others, which no one but them can understand? Is it possible for a group of people to play a (card-less) game of Poker on the telephone, without anyone being able to cheat? Can you convince others that you can solve a tough math (or SudoKu) puzzle, without giving them the slightest hint of your solution? These questions (and their remarkable answers) are in the realm of modern cryptography. In this talk I plan to survey some of the mathematical and computational ideas, definitions and assumptions which underlie privacy and security of the Internet and electronic commerce. We shall see how these lead to solutions of the questions above and many others. I will also explain the fragility of the current foundations of modern cryptography, and the need for stronger ones. No special background will be assumed.
Randomness - the Utility of Unpredictability
Thursday, May 10, 2012, 20:15 h Auditorium Maximum, HG F 30
Is the universe inherently deterministic or probabilistic? Perhaps more importantly - can we tell the difference between the two? Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling... Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from "unpredictable" phenomena like the weather or the stock market? A computational theory of randomness, developed in the past three decades, reveals (perhaps counter-intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I'll explain the main ideas and results of this theory. The talk is aimed at a general audience, and no particular background will be assumed.