Avi Wigderson Institue for Advanced Study |

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 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.
Bio: Avi Wigderson is a Professor at the School of Mathematics, Institute for Advanced Study, Princeton. His research interests include: Complexity Theory, Parallel Computation, Combinatorics and Graph Theory, Combinatorial Optimization Algorithms, Randomness and Cryptography, Distributed and Neural Networks. Avi’s honors include: 2009 G¨odel Prize, 2008 Conant Prize, 2008 Gibbs Lecture, San Diego,California, 2006 ICM Plenary Lecture, Madrid, Spain, The Yoram Ben-Porat Presidential Prize for Outstanding Researcher , 1994 Nevanlinna Prize and 1994 & 1990 Invited speaker at the International Congress of Mathematicians. |

4:15pm B17 Upson Hall Thursday, September 17, 2009 Refreshments at 3:45pm in the Upson 4th Floor Atrium |

Computer Science & Information Science Colloquium Fall 2009 |

www.cs.cornell.edu/events/colloquium |

www.cs.cornell.edu/events/colloquium |