The Power and Weakness of Randomness in Computation
Speaker: Professor Avi Wigderson , Institute for Advanced Study
Date: November 10 2005
Time: 4:00PM to 5:30PM
Location: 32-123
Host: Victor Zue, CSAIL
Contact: Victoria Palay, 617-253-8924, palay@csail.mit.edu
Relevant URL: 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.
Biography
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).
See other events that are part of Dertouzos Lecturer Series 2005/2006
See other events happening in November 2005
