IC Colloquium : Randomness and pseudorandomness
Event details
| Date | 20.09.2013 |
| Hour | 15:15 › 16:30 |
| Speaker | Avi Widgerson - Institute for Advanced Study, Princeton |
| Location | |
| Category | Conferences - Seminars |
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?
Pseudorandomness - a computational theory of randomness, developed in the past three decades, studies deterministic structures with random-like behavior, and turns out to underlie fundamental problems in a variety of mathematics, computer science and engineering areas. This theory also reveals (perhaps counter-intuitively) that almost all applications designed to work under perfect randomness actually survive in weakly random or even completely deterministic worlds. In the talk I'll explain the main ideas and results of this theory.
Biography
Avi Wigderson did his undergraduate studies at the Technion in Haifa, Israel. He graduated in 1980, and went on to graduate study at Princeton University. In 1983 he received his PhD for work in computational complexity. After this, he held positions at U.C Berkeley, IBM Research in San Jose, MSRI in Berkeley, at Princeton University, the Hebrew University in Jerusalem, and Tel Aviv University. Since 1999 he has a position at the Institute for Advanced Study, which is currently his full time residence. Avi Wigderson works in the areas of Randomness and Computation, Complexity Theory, Combinatorics and Graph Theory, and many others. He received the Nevanlinna Prize in 1994 for his work on computational complexity. In 2009, he won the Gödel Prize. He was an invited speaker at the International Congress of Mathematicians in 1990 and 1994, and gave a plenary talk at the International Congress of Mathematicians in 2006.
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?
Pseudorandomness - a computational theory of randomness, developed in the past three decades, studies deterministic structures with random-like behavior, and turns out to underlie fundamental problems in a variety of mathematics, computer science and engineering areas. This theory also reveals (perhaps counter-intuitively) that almost all applications designed to work under perfect randomness actually survive in weakly random or even completely deterministic worlds. In the talk I'll explain the main ideas and results of this theory.
Biography
Avi Wigderson did his undergraduate studies at the Technion in Haifa, Israel. He graduated in 1980, and went on to graduate study at Princeton University. In 1983 he received his PhD for work in computational complexity. After this, he held positions at U.C Berkeley, IBM Research in San Jose, MSRI in Berkeley, at Princeton University, the Hebrew University in Jerusalem, and Tel Aviv University. Since 1999 he has a position at the Institute for Advanced Study, which is currently his full time residence. Avi Wigderson works in the areas of Randomness and Computation, Complexity Theory, Combinatorics and Graph Theory, and many others. He received the Nevanlinna Prize in 1994 for his work on computational complexity. In 2009, he won the Gödel Prize. He was an invited speaker at the International Congress of Mathematicians in 1990 and 1994, and gave a plenary talk at the International Congress of Mathematicians in 2006.
Links
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Aleksander Madry