The Power and Weakness of Randomness (When You are Short on Time)

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.

About the Speaker:

Avi Wigderson received his Ph.D. in computer science in 1983 from Princeton University. Since then he has held permanent positions at the Hebrew University Computer Science Institute, where he was the chair from 1992-95, and at the Institute for Advanced Study School of Math, heading their Computer Science and Discrete Math Program since 1999. He has held visiting positions at the University of California, Berkeley, IBM Research, the Mathematical Sciences Research Institute, Princeton University and the Institute for Advanced Study.

Wigderson’s research interests include computational complexity theory, algorithms, parallel and distributed computation, combinatorics and graph theory, cryptography, randomness and pseudorandomness.

Honors include being a two-time invited speaker at the International Congress of Mathematicians, where he was presented in 1994 with the Nevanlinna Prize for outstanding contributions in mathematical aspects of information sciences. Widgerson was an invited speaker at the AMS Gibbs Lectures and the recipient of the Conant Prize. Most recently, Wigderson was the honored recipient of the 2009 Gödel Prize, which recognizes outstanding papers in theoretical computer science.

Homepage: http://www.math.ias.edu/avi/