Randomness |
||
|
||
|
DESCRIPTION/ABSTRACT: This talk by Institute of Advanced Study mathematics professor Avi Wigderson is a CSE Colloquium and part of the CSE department's Winter 2015 Distinguished Lecture Series. 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. SPEAKER BIO: Avi Wigderson is one of the most prolific and influential researchers in the theory of computation. He has made fundamental contributions to circuit complexity, parallel algorithms,cryptography (in articular, to zero-knowledge proofs and private multi-party computation), the role of randomness in computation, proof complexity, and connections between complexity and combinatorics. He earned his Ph.D. in computer science at Princeton University in 1983, studying with Prof. Richard Lipton. He was a professor at the Hebrew University from 1986 to 2003, since when he has been Faculty at the prestigious Institute for Advanced Study in Princeton. Among many other honors, he received the 1994 Nevanlinna Prize and (jointly with Reingold and Vadhan) the 2009 Godel Prize for his work on the zig-zag graph product. He has been elected to be a member of the National Academy of Sciences. |
