skip to content
 

The power and weakness of randomness, when you are short on time (Rothschild Lecture)

Presented by: 
A Wigderson [IAS, Princeton]
Date: 
Monday 28th March 2011 - 17:00 to 18:00
Venue: 
INI Seminar Room 1
Abstract: 
Man 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'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms efficient. Time permitting, I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons