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 (conflicting?) 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 of the Speaker

Research Interests:

Complexity Theory, Parallel Computation, Combinatorics and Graph Theory,

Combinatorial Optimization Algorithms, Randomness and Cryptography,

Distributed and Neural Networks

Honors:

• 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

• 1994 Invited speaker at the International Congress of Mathematicians, Zurich, Switzerland

• 1990 Invited speaker at the International Congress of Mathematicians, Kyoto, Japan

• 1989 Bergman Fellowship

• 1986-89 Alon Fellowship

• 1982-83 IBM Graduate Fellowship, Princeton University

• 1977-80 President’s List of Excellence, The Technion

Education:

• 1980 - 1983 Ph.D. in Computer Science, Princeton University

• 1977 - 1980 B.Sc in Computer Science, Technion, Haifa, Israel

Permanent Positions:

• 1999 - Institute for Advanced Study, Princeton

• 1986 - 2003 Computer Science Institute, Hebrew University, Jerusalem

Visiting Positions:

• 1995 - 1996 Institute for Advanced Study and Princeton University

• 1990 - 1992 Princeton University

• 1985 - 1986 Mathematical Sciences Research Institute, Berkeley, California

• 1984 - 1985 IBM Research, San Jose, California