- Series
- School of Mathematics Colloquium
- Time
- Thursday, November 10, 2011 - 11:00am for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Avi Wigderson – School of Mathematics, Institute for Advanced Study
- Organizer
- Prasad Tetali
Please Note: This is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011
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 faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.