The case is legendary: in the Second World War the German armed forces encrypted their messages so cunningly that the Allies had no chance of protecting their warships against German U-boat attacks. But then the mathematician Alan Turing arrived on the scene and broke the code, marking a turning point in the war at sea. Encryption techniques have become somewhat more complex since then. Nonetheless, even today no mathematician or computer scientist is able to prove that a particular code cannot be cracked.

Congruously this year’s Wolfgang Pauli Lectures will be dedicated to Alan Turing, the father of computing, on the hundredth anniversary of his birth. These lectures will be hold by Avi Wigderson, professor of Mathematics at the Institute for Advanced Study in Princeton. 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.

Computation theory has revolutionized our lives

Avi Wigderson is someone who unlocks the secrets of Internet security and explores the limits of human knowledge. Anyone who follows the Israeli mathematician’s thinking will sail to far horizons, because the problems he deals with are major and fundamental. Just listening to Avi Wigderson is an experience: not only is he sharp-witted, he is also a skilful orator (see Avi Wigderson’s video lectures).

“His results are astonishing every time, but he presents them in such an electrifying manner that one can easily and gladly follow him every step of the way”, says Thomas Holenstein, Assistant Professor at the Institute of Theoretical Computer Science. Like Wigderson, Holenstein carries out research in the field of computational complexity theory. Computational complexity theory, studying the power and limits of computing systems, provides the mathematical foundations of computer science and technology.

«The advent of computation theory, followed by computing practice, has completely revolutionized our lives. Common objects of other disciplines, including mathematics and the sciences, often reveal new facets when viewed through the computational lens», says Avi Wigderson. «In this series of three lectures I plan to explain some central aspects of this extensive theory, and their consequences and challenges.»

Wolfgang Pauli Lectures 2012

The Wolfgang Pauli Lectures are an annual lecture series that is devoted alternatingly to Physics, Mathematics and Biology. They are named after the great theoretical physicist and Nobel laureat Wolfgang Pauli, who was professor at ETH Zürich from 1928 until his death in 1958. The first Wolfgang Pauli Lectures were given in 1962 by Max Delbrück, and over the years there have been many eminent speakers, including a number of Nobel laureats.
All lectures take place in the Auditorium Maximum, ETH Zurich, HG F 30. The lectures are all in English and do not assume any specialist knowledge or particular background.

First lecture: 7 May, 20:15 hrs
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits to Human Knowledge
Abstract:
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 Avi Wigderson will attempt to describe its mathematical, scientific and philosophical content. He 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) .

Second lecture: 8 May, 20:15 hrs
Cryptography: Secrets and Lies, Knowledge and Trust
Abstract:
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 Avi Wigderson plans to survey some of the mathematical and computational ideas, definitions and assumptions which underlie privacy and security of the Internet and electronic commerce.
Avi Wigderson will show how these lead to solutions of the questions above and many others. He will also explain the fragility of the current foundations of modern cryptography, and the need for stronger ones.

Third lecture: 10 May, 20:15 hrs
Randomness - the Utility of Unpredictability
Abstract:
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 Avi Wigderson will explain the main ideas and results of this theory.