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