Professor Avi Wigderson from the Institute for Advanced Study at Princeton gave a talk titled
"The Power and Weakness of Randomness in Computation" on November 10th, 2005.
Abstract:
Humanity has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I will talk about two main aspects of this research on randomness, demonstrating its power and weakness respectively.
(1) Randomness is paramount to computational efficiency: I will show how the use of randomness can dramatically speed up computation (and do other wonders) for a variety of problems and settings.
(2) Computational efficiency is paramount to understanding randomness: I will explain the new, computationally-motivated definition of randomness, and try to argue its merits as the "right" definition. I will then show how such randomness may be generated deterministically, from computationally difficult problems.
Bio:
Avi Wigderson obtained his B.Sc. in Computer Science from the Technion in 1980, and his Ph.D. from Princeton in 1983. He was a member of the faculty at the Hebrew University in Jerusalem from 1986-2003, and is currently a member of the Mathematics Faculty at the Institute for Advanced Study at Princeton. His research interests lie principally in Complexity Theory, Algorithms, Randomness, and Cryptography. His awards include the Yoram Ben-Porat Presidential Prize for Outstanding Researcher, and the Nevanlinna Prize (2004).
For more information:
Professor Deborah Estrin's home page
CSAIL Dertouzos Lecturer Series Archive